1091. 二进制矩阵中的最短路径
# 1091. 二进制矩阵中的最短路径 (opens new window)
# 1.BFS
解题思路：使用广搜的核心在于，每一轮遍历搜索当前节点下一步能走到的所有位置，有点类似于贪心。而visited数组之所以能够用全局的，是因为广搜不会对当前搜索过的节点进行回溯，所以当前节点搜索过后不需要将visited复原。往后遍历时如果发现当前节点已经被搜索过了，那么说明前面该节点已经出现过了，第一次出现时记录的路径就是起始节点到当前节点最短的路径。
采用队列保存每一个大圈的节点数(每一轮遍历的所有节点)。每轮遍历时(需要保存当前这轮的节点数)，搜索队列每个节点周围一圈八个位置是否满足条件，
class Solution {
int n;
public int shortestPathBinaryMatrix(int[][] grid) {
Deque<int[]> deque = new LinkedList<>();
if (grid[0][0] == 1) return -1;
if (grid.length == 1) {
return 1;
}
n = grid.length;
int[][] dir = new int[][]{{0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}, {-1, 0}, {-1, 1}};
boolean[][] visited = new boolean[n][n];
int ans = 1;
deque.offerLast(new int[]{0, 0});
while (!deque.isEmpty()) {
int size = deque.size();
for (int iteration = 0; iteration < size; iteration++) {
int[] curr = deque.pollFirst();
int x = curr[0];
int y = curr[1];
for (int i = 0; i < 8; i++) {
int nx = x + dir[i][0];
int ny = y + dir[i][1];
if (check(nx, ny) && !visited[nx][ny] && grid[nx][ny] == 0) {
if (nx == n - 1 && ny == n - 1) return ans + 1;
deque.offerLast(new int[]{nx, ny});
visited[nx][ny]=true;
}
}
}
ans++;
}
return -1;
}
public boolean check(int x, int y) {
if (x >= 0 && x < n && y >= 0 && y < n) return true;
return false;
}
}
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
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
# 2.DFS
😭😭😭超时了没过，仅分享思路。每次遍历八个方向，深搜后需要将访问位回溯。
剪枝：主要针对斜对角节点的优化。dir数组保存当前节点斜方向路径优化后的方向；遍历时下一个节点dir的状态需要根据当前节点能够走的所有方向(temp数组保存)进行更新。
举个例子：
0 0 1
0 0 0
0 0 0
1
2
3
2
3
假设当前节点为方阵的中心，显然除了右上角方向不能够走之外，其它方向都可以走。因为上可以走，所以左上角节点(0,0)进行搜索时，不需要再往右边走，显然(1,1)直接往上遍历直接一步到位了。
但还需要继续剪枝，否则依旧容易超时。
class Solution {
int ans=1;
int res=Integer.MAX_VALUE;
int n;
public int shortestPathBinaryMatrix(int[][] grid) {
n=grid.length;
boolean[][] visited=new boolean[n][n];
//右下左上
boolean[] dir=new boolean[8];
dir[0]=true;
dir[1]=true;
dir[2]=true;
if(grid[0][0]==1) return -1;
dfs(grid,visited,dir,0,0);
res=res==Integer.MAX_VALUE?-1:res;
return res;
}
public void dfs(int[][] grid,boolean[][] visited,boolean[] dir,int x,int y){
if(x==n-1&&y==n-1){
res=ans<res?ans:res;
return ;
}
boolean[] temp=new boolean[8];
if(check(x,y+1)&&!visited[x][y+1]&&grid[x][y+1]==0&&dir[0]){
temp[0]=true;
}
if(check(x+1,y+1)&&!visited[x+1][y+1]&&grid[x+1][y+1]==0&&dir[1]){
temp[1]=true;
}
if(check(x+1,y)&&!visited[x+1][y]&&grid[x+1][y]==0&&dir[2]){
temp[2]=true;
}
if(check(x+1,y-1)&&!visited[x+1][y-1]&&grid[x+1][y-1]==0&&dir[3]){
temp[3]=true;
}
if(check(x,y-1)&&!visited[x][y-1]&&grid[x][y-1]==0&&dir[4]){
temp[4]=true;
}
if(check(x-1,y-1)&&!visited[x-1][y-1]&&grid[x-1][y-1]==0&&dir[5]){
temp[5]=true;
}
if(check(x-1,y)&&!visited[x-1][y]&&grid[x-1][y]==0&&dir[6]){
temp[6]=true;
}
if(check(x-1,y+1)&&!visited[x-1][y+1]&&grid[x-1][y+1]==0&&dir[7]){
temp[7]=true;
}
//开始走
if(temp[0]){
refresh(dir);
if(temp[1]) dir[2]=false;
if(temp[7]) dir[6]=false;
if(temp[6]) dir[5]=false;
if(temp[2]) dir[3]=false;
visited[x][y+1]=true;
ans++;
dfs(grid,visited,dir,x,y+1);
ans--;
visited[x][y+1]=false;
}
if(temp[1]){
refresh(dir);
if(temp[0]) dir[6]=false;
if(temp[2]) dir[4]=false;
visited[x+1][y+1]=true;
ans++;
dfs(grid,visited,dir,x+1,y+1);
ans--;
visited[x+1][y+1]=false;
}
if(temp[2]){
refresh(dir);
if(temp[1]) dir[0]=false;
if(temp[3]) dir[4]=false;
if(temp[0]) dir[7]=false;
if(temp[4]) dir[5]=false;
visited[x+1][y]=true;
ans++;
dfs(grid,visited,dir,x+1,y);
ans--;
visited[x+1][y]=false;
}
if(temp[3]){
refresh(dir);
if(temp[2]) dir[0]=false;
if(temp[4]) dir[6]=false;
visited[x+1][y-1]=true;
ans++;
dfs(grid,visited,dir,x+1,y-1);
ans--;
visited[x+1][y-1]=false;
}
if(temp[4]){
refresh(dir);
if(temp[3]) dir[2]=false;
if(temp[5]) dir[6]=false;
if(temp[6]) dir[7]=false;
if(temp[2]) dir[1]=false;
visited[x][y-1]=true;
ans++;
dfs(grid,visited,dir,x,y-1);
ans--;
visited[x][y-1]=false;
}
if(temp[5]){
refresh(dir);
if(temp[4]) dir[2]=false;
if(temp[6]) dir[0]=false;
visited[x-1][y-1]=true;
ans++;
dfs(grid,visited,dir,x-1,y-1);
ans--;
visited[x-1][y-1]=false;
}
if(temp[6]){
refresh(dir);
if(temp[5]) dir[4]=false;
if(temp[7]) dir[0]=false;
if(temp[0]) dir[1]=false;
if(temp[4]) dir[3]=false;
visited[x-1][y]=true;
ans++;
dfs(grid,visited,dir,x-1,y);
ans--;
visited[x-1][y]=false;
}
if(temp[7]){
refresh(dir);
if(temp[6]) dir[4]=false;
if(temp[0]) dir[2]=false;
visited[x-1][y+1]=true;
ans++;
dfs(grid,visited,dir,x-1,y+1);
ans--;
visited[x-1][y+1]=false;
}
}
public void refresh(boolean[] dir){
for(int i=0;i<8;i++){
dir[i]=true;
}
}
public boolean check(int x,int y){
if(x>=0&&x<n&&y>=0&&y<n) return true;
return false;
}
}
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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
编辑 (opens new window)
上次更新: 2023/12/15, 15:49:57