牛可乐有一个行列的迷宫,如果是’#’,代表第行第列的方格为墙壁,如果是’.’,代表第行第列的方格为可走方格。 每一步移动在一个可走方格,可以水平的或者垂直的移动到相邻的一个可走方格中。 但是不能走出迷宫,不能走到一个墙壁方格,也不能对角线方向移动。 你可以选择任意一个起点方格和终点方格(这两个方格必须为可走方格,且可以相互到达)。 牛可乐将从你选择的起点方格用最小的步数移动到终点方格。 本题需要你最优的选择起点方格和终点方格后让牛可乐必须要移动的步数尽可能大,你需要计算这个步数的最大值。-笔试面试资料
这是qklbishe.com第6233 篇笔试面试资料
提供答案分析,通过本文《牛可乐有一个行列的迷宫,如果是’#’,代表第行第列的方格为墙壁,如果是’.’,代表第行第列的方格为可走方格。 每一步移动在一个可走方格,可以水平的或者垂直的移动到相邻的一个可走方格中。 但是不能走出迷宫,不能走到一个墙壁方格,也不能对角线方向移动。 你可以选择任意一个起点方格和终点方格(这两个方格必须为可走方格,且可以相互到达)。 牛可乐将从你选择的起点方格用最小的步数移动到终点方格。 本题需要你最优的选择起点方格和终点方格后让牛可乐必须要移动的步数尽可能大,你需要计算这个步数的最大值。-笔试面试资料》可以理解其中的代码原理,这是一篇很好的求职学习资料
本站提供程序员计算机面试经验学习,笔试经验,包括字节跳动/头条,腾讯,阿里,美团,滴滴出行,网易,百度,京东,小米,华为,微软等互联网大厂真题学习背诵。
答案:
牛可乐有一个行
列的迷宫,如果
是’#’,代表第
行第
列的方格为墙壁,如果
是’.’,代表第
行第
列的方格为可走方格。
每一步移动在一个可走方格,可以水平的或者垂直的移动到相邻的一个可走方格中。
但是不能走出迷宫,不能走到一个墙壁方格,也不能对角线方向移动。
你可以选择任意一个起点方格和终点方格(这两个方格必须为可走方格,且可以相互到达)。
牛可乐将从你选择的起点方格用最小的步数移动到终点方格。
本题需要你最优的选择起点方格和终点方格后让牛可乐必须要移动的步数尽可能大,你需要计算这个步数的最大值。
遍历所有的“起点”可能性,针对每个“起点”进行宽度优先搜索,计算离所有可到达“终点”的步数,选择出其中最大的步数即可。不过这种题目,真心运行得慢,python几乎都超时,还是得Java或者C++。
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.Queue; import java.util.ArrayDeque; public class Main { // 要求的最大步数 static int maxSteps = 0; // 四个方向的坐标变化 static int[][] orientation = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 迷宫行数和列数 static int n, m; // 迷宫矩阵 static char[][] grid; // 动规矩阵 static int[][] dp; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] strNM = br.readLine().trim().split(" "); n = Integer.parseInt(strNM[0]); m = Integer.parseInt(strNM[1]); grid = new char[n][m]; for(int i = 0; i < n; i++){ char[] row = br.readLine().trim().toCharArray(); for(int j = 0; j < m; j++) grid[i][j] = row[j]; } // 遍历所有坐标,对可能的起点进行宽搜 for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ if(grid[i][j] == '.'){ dp = new int[n][m]; // 对于每个起点,都需要新的dp bfs(i, j); } } } System.out.println(maxSteps); } private static void bfs(int startX, int startY) { Queue<int[]> queue = new ArrayDeque(); queue.offer(new int[]{startX, startY}); // dp还需要一位来表示该坐标是否被访问过,0表示未被访问过 dp[startX][startY] = 1; // 各种尝试,计算走到能达到的终点需要多少步 while(!queue.isEmpty()){ int[] point = queue.poll(); // 取出队首的坐标,然后对能走的四个方向进行尝试 for(int i = 0; i < 4; i++){ int endX = point[0] + orientation[i][0]; int endY = point[1] + orientation[i][1]; // 如果终点位置合法且没有被访问过,则更新一下步数 if(endX >= 0 && endX < n && endY >= 0 && endY < m && grid[endX][endY] != '#' && dp[endX][endY] == 0){ dp[endX][endY] = dp[point[0]][point[1]] + 1; queue.offer(new int[]{endX, endY}); } } } for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ // 由于用0来表示未访问了,因此距离要减1 maxSteps = Math.max(maxSteps, dp[i][j] - 1); } } } }
今天 14:27:27 回复(0)
文章部分来自互联网,侵权联系删除
www.qklbishe.com
区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站部分资料来自网络,侵权联系删除!资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 牛可乐有一个行列的迷宫,如果是’#’,代表第行第列的方格为墙壁,如果是’.’,代表第行第列的方格为可走方格。 每一步移动在一个可走方格,可以水平的或者垂直的移动到相邻的一个可走方格中。 但是不能走出迷宫,不能走到一个墙壁方格,也不能对角线方向移动。 你可以选择任意一个起点方格和终点方格(这两个方格必须为可走方格,且可以相互到达)。 牛可乐将从你选择的起点方格用最小的步数移动到终点方格。 本题需要你最优的选择起点方格和终点方格后让牛可乐必须要移动的步数尽可能大,你需要计算这个步数的最大值。-笔试面试资料
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 牛可乐有一个行列的迷宫,如果是’#’,代表第行第列的方格为墙壁,如果是’.’,代表第行第列的方格为可走方格。 每一步移动在一个可走方格,可以水平的或者垂直的移动到相邻的一个可走方格中。 但是不能走出迷宫,不能走到一个墙壁方格,也不能对角线方向移动。 你可以选择任意一个起点方格和终点方格(这两个方格必须为可走方格,且可以相互到达)。 牛可乐将从你选择的起点方格用最小的步数移动到终点方格。 本题需要你最优的选择起点方格和终点方格后让牛可乐必须要移动的步数尽可能大,你需要计算这个步数的最大值。-笔试面试资料