点击关注公众号，干货第一时间送达
这题还是 "矩阵" 类型题目，
看起来像是 "图" 的，
其实，有点差别，
因为这题没有多路连通。
一起来看看。
一、屏幕前的吴彦祖和刘亦菲们，请听题
举个例子：
如上图，就是求这样一条路径值。
诸位应该遇到过类似的题目，
不难，
利用广度遍历即可。
二、解题
这里呢，我们可以创建记录矩阵 map[][]，
用于记录从出发点（0,0）
到达当前点（x,y）的最短路径值 map[x][y]，
初始的时候，map[0][0] = 1
利用队列，广度遍历原矩阵 matrix[][] 的元素，
并且需要判断当前点（x,y）的上、下、左、右 四个相邻点，
是否可以走：
在代码中，可以通过方法调用实现：
当前，也可以写成 for 循环的形式，
都可以，原理是一样的。
最后，到达矩阵右下角，
也就是 matrix[M-1][N-1]，
返回记录值 map[M-1][N-1] 即可：
看看代码。
完整代码：
public class CodingDemo_03 {
/**
* 最短通路值
* @param matrix
* @return
*/
private static int minPathValue(int[][] matrix){
if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0
|| matrix[matrix.length-1][matrix[0].length-1] != 1){
return 0;
}
int M = matrix.length;
int N = matrix[0].length;
//1，创建记录数组，记录到达每个位置最短路径值
int[][] map = new int[M][N];
map[0][0] = 1;
//2,创建队列，用于广度遍历
//队列值 int[]，分别表示矩阵中元素（x,y）的坐标值
Deque<int[]> queue = new LinkedList<>();
queue.offerLast(new int[]{0,0});
//3,开始广度遍历
while (!queue.isEmpty()){
//4，当前位置(x，y),初始的时候，从原点（0,0）出发，map记录已经存在
int[] cell = queue.pollFirst();
int x = cell[0];
int y = cell[1];
//到达终点
if (x == M-1 && y == N-1){
return map[x][y];
}
//记录到达当前点的路径值
int pre = map[x][y];
//5,遍历当前点，上、下、左、右 四个相邻格子的点
bfs(matrix, map, queue, pre, x-1, y);
bfs(matrix, map, queue, pre, x, y+1);
bfs(matrix, map, queue, pre, x+1, y);
bfs(matrix, map, queue, pre, x, y-1);
}
return 0;
}
private static void bfs(int[][] matrix, int[][] map, Deque<int[]> queue, int pre, int x, int y){
//剔除越界的点，matrix[x][y] != 1 无效点，和 map[x][y] != 0 已经走过的点
if (x < 0 || x >= matrix.length || y < 0 || y >= matrix[0].length ||
matrix[x][y] != 1 || map[x][y] != 0){
return;
}
//设置当前点的路径值
map[x][y] = pre+1;
//加入队列，用于bfs遍历
queue.offerLast(new int[]{x,y});
}
public static void main(String[] args) {
int[][] matrix = {
{1,0,1,1,1},
{1,0,1,0,1},
{1,1,1,0,1},
{0,0,0,0,1},
};
System.out.println(minPathValue(matrix));
}
}
输出：
D:\java\bin\java.exe
12
文章转载自皮皮克克，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。
