05 August 2008
01矩阵只能走0，找从左上到右下最短路径，可以走斜线，共八个方向
1.如果只是要找到某一个结果是否存在，那么DFS会更高效。因为DFS会首先把一种可能的情况尝试到底，才会回溯去尝试下一种情况，只要找到一种情况，就可以返回了。但是BFS必须所有可能的情况同时尝试，在找到一种满足条件的结果的同时，也尝试了很多不必要的路径；
2.如果是要找所有可能结果中最短的，那么BFS回更高效。因为DFS是一种一种的尝试，在把所有可能情况尝试完之前，无法确定哪个是最短，所以DFS必须把所有情况都找一遍，才能确定最终答案（DFS的优化就是剪枝，不剪枝很容易超时）。而BFS从一开始就是尝试所有情况，所以只要找到第一个达到的那个点，那就是最短的路径，可以直接返回了，其他情况都可以省略了，所以这种情况下，BFS更高效。
BFS
自己习惯的BFS写法，入队的时候做各种检查和标记，用不用visited数组来标记都可以，这里没用，修改原地的值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
int[][] dirs = { {-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1} };
public int shortestPathBinaryMatrix(int[][] grid) {
int steps = 0;
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return steps;
}
if (grid[0][0] == 1) {
return -1;
}
int rows = grid.length;
int cols = grid[0].length;
Queue<int[]> queue = new ArrayDeque<>();
queue.offer(new int[]{0, 0});
steps++;
grid[0][0] = 2;
// 入队的时候做检查和标记
if (rows - 1 == 0 && cols - 1 == 0) {
return steps;
}
while (!queue.isEmpty()) {
int oneLevel = queue.size();
steps++;
for (int i = 0; i < oneLevel; i++) {
int[] curr = queue.poll();
int currX = curr[0];
int currY = curr[1];
for (int[] dir : dirs) {
int newX = currX + dir[0];
int newY = currY + dir[1];
if (newX >= 0 && newX < rows && newY >= 0 && newY < cols && grid[newX][newY] == 0) {
// 入队的时候做检查和标记
if (newX == rows - 1 && newY == cols - 1) {
return steps;
}
grid[newX][newY] = 2;
queue.offer(new int[]{newX, newY});
}
}
}
}
return -1;
}
}
参考别的人的写法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class shortestPathBinaryMatrix {
private static int[][] directions = { {0,1}, {0, -1}, {1, -1}, {1, 0}, {1, 1}, {-1, -1}, {-1, 0}, {-1, 1} };
private int row, col;
public int shortestPathBinaryMatrix(int[][] grid) {
row = grid.length;
col = grid[0].length;
if(grid[0][0] == 1 || grid[row - 1][col - 1] == 1) return -1;
Queue<int[]> pos = new LinkedList<>();
grid[0][0] = 1; // 直接用grid[i][j]记录从起点到这个点的最短路径长。按照题意 起点也有长度1
pos.add(new int[]{0,0});
while(!pos.isEmpty() && grid[row - 1][col - 1] == 0){ // 求最短路径 使用BFS
int[] xy = pos.remove();
int preLength = grid[xy[0]][xy[1]]; // 当前点的路径长度
for(int i = 0; i < 8; i++){
int newX = xy[0] + directions[i][0];
int newY = xy[1] + directions[i][1];
if(inGrid(newX, newY) && grid[newX][newY] == 0){
pos.add(new int[]{newX, newY});
grid[newX][newY] = preLength + 1; // 下一个点的路径长度要+1
}
}
}
return grid[row - 1][col - 1] == 0 ? -1 : grid[row - 1][col - 1]; // 如果最后终点的值还是0，说明没有到达
}
private boolean inGrid(int x, int y){
return x >= 0 && x < row && y >= 0 && y < col;
}
}