【BFS】
在一个 N × N 的方形网格中，每个单元格有两种状态：空（0）或者阻塞（1）。
一条从左上角到右下角、长度为 k 的畅通路径，由满足下述条件的单元格 C_1, C_2, ..., C_k 组成：
- 相邻单元格
C_i 和 C_{i+1} 在八个方向之一上连通（此时，C_i 和 C_{i+1} 不同且共享边或角）
C_1 位于 (0, 0)（即，值为 grid[0][0]）C_k 位于 (N-1, N-1)（即，值为 grid[N-1][N-1]）- 如果
C_i 位于 (r, c)，则 grid[r][c] 为空（即，grid[r][c] == 0）返回这条从左上角到右下角的最短畅通路径的长度。如果不存在这样的路径，返回 -1 。
看图更直观
Example:
示例 1：
输入：[[0,1],[1,0]]
输出：2
示例 2：
输入：[[0,0,0],[1,1,0],[1,1,0]]
输出：4
提示：
1 <= grid.length == grid[0].length <= 100grid[i][j] 为 0 或 1
Analysis
简单的寻路算法，可以为地图包裹一圈“墙”简化寻找邻居的步骤
代码不够简洁，但是蛮直观的
Solution 【BFS】
执行用时 :75 ms, 在所有Java提交中击败了100.00%的用户
内存消耗 :55.9 MB, 在所有Java提交中击败了100.00%的用户
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
|
class Solution {
private boolean[][] map;
private boolean[][] isVisited;
private Node destNode;
public int shortestPathBinaryMatrix(int[][] grid) {
if (grid[0][0] == 1) return -1;
parse(grid); // 为四周包裹障碍物
int row = map.length;
int col = map[0].length;
// System.out.println("=============TEST MAP================");
// for(int i = 0; i < row; i++) {
// for (int j = 0; j < col; j++) {
// System.out.print( (map[i][j] ? 0 : 1) + " ");
// }
// System.out.println();
// }
// System.out.println("=============TEST MAP================");
isVisited = new boolean[row][col];
destNode = new Node(row-2, col-2);
isVisited[1][1] = true;
int res= bfs(1, 1);
//
return res;
}
private int bfs(int iniX, int iniY) {
Queue<Node> queue = new LinkedList<>();
Node start = new Node(iniX, iniY);
start.setMove(1);
queue.offer(start);
while (!queue.isEmpty()) {
Node cur = queue.poll();
// System.out.println("At (" + cur.x + ", " + cur.y + ")");
if (cur.equals(destNode)) {
return cur.move;
}
int nextMove = cur.move + 1;
for (Node neighbor : getNeighbors(cur)) {
neighbor.setMove(nextMove);
queue.offer(neighbor);
isVisited[neighbor.x][neighbor.y] = true;
}
}
return -1;
}
private Iterable<Node> getNeighbors(Node node) {
Stack<Node> stack = new Stack<>();
short x = node.x;
short y = node.y;
if (map[x-1][y-1] && !isVisited[x-1][y-1]) {
stack.push(new Node(x-1, y-1));
}
if (map[x-1][y] && !isVisited[x-1][y]) {
stack.push(new Node(x-1, y));
}
if (map[x-1][y+1] && !isVisited[x-1][y+1]) {
stack.push(new Node(x-1, y+1));
}
if (map[x][y-1] && !isVisited[x][y-1]) {
stack.push(new Node(x, y-1));
}
if (map[x][y+1] && !isVisited[x][y+1]) {
stack.push(new Node(x, y+1));
}
if (map[x+1][y-1] && !isVisited[x+1][y-1]) {
stack.push(new Node(x+1, y-1));
}
if (map[x+1][y] && !isVisited[x+1][y]) {
stack.push(new Node(x+1, y));
}
if (map[x+1][y+1] && !isVisited[x+1][y+1]) {
stack.push(new Node(x+1, y+1));
}
// System.out.println("number of neighbors:" + stack.size());
return stack;
}
private class Node{
short x;
short y;
short move;
public Node(int x, int y) {
this.x = (short)(x);
this.y = (short)(y);
}
public short getMove() {
return move;
}
public void setMove(int move) {
this.move = (short)(move);
}
public boolean equals(Node that) {
return this.x == that.x && this.y == that.y;
}
}
private void parse(int[][] grid) {
int row = grid.length;
int col = grid[0].length;
map = new boolean[row + 2][col + 2];
for (int i = 0; i < col + 2; i++) {
map[0][i] = false;
map[row+1][i] = false;
}
for (int i = 0; i < row; i++) {
map[i+1][0] = false;
map[i+1][col+1] = false;
for (int j = 0; j < col; j++)
map[i+1][j+1] = grid[i][j] == 0;
}
}
}
|
复杂度分析
和地图尺寸正相关
时间：$O()$
空间：$O()$
Solution
参考了这位朋友的代码，寻找邻居部分很简洁，码住记录
作者：ftcl_lx链接 侵删
class Solution {
public int shortestPathBinaryMatrix(int[][] grid) {
int row = grid.length;
int col = grid[0].length;
if(grid[row-1][col-1] == 1 || grid[0][0] == 1)
return -1;
return bfs(grid);
}
int bfs(int[][] grid) {
boolean[][] visit = new boolean[grid.length][grid[0].length];
Node node = new Node(0,0,1);
visit[0][0] = true;
LinkedList<Node> queue = new LinkedList<>();
queue.push(node);
int x[] = {-1, -1, -1, 0, 1, 1, 1, 0};
int y[] = {-1, 0, 1, 1, 1, 0, -1, -1};
while(!queue.isEmpty()){
Node root = queue.removeFirst();
int val = root.value;
if(root.x == grid.length - 1 && root.y == grid[0].length - 1) {
return root.value;
}
for(int i = 0; i < x.length; i++) {
int row = root.x + x[i];
int col = root.y + y[i];
if(row >=0 && col >=0 && row < grid.length && col < grid[0].length && grid[row][col] == 0 && !visit[row][col]){
queue.add(new Node(row,col,val+1));
visit[row][col] = true;
}
}
}
return -1;
}
}
class Node{
int x;
int y;
int value;
public Node(int x, int y, int value){
this.x = x;
this.y = y;
this.value = value;
}
}