多源广度优先搜索
广度优先搜索进阶题目
简单而言，多源广度优先搜索的起始节点比较多，与普通的广度优先搜索不同，多源强调的是开始搜索的源头不是1，在初始将起点放入待搜索队列时，需要将所有符合条件的待搜索节点全部入队
核心做法
在初次遍历整张图的时候，将所有符合条件的待搜索节点(源节点)放入队列中，每次取出节点后都需要搜索当前节点的上下左右四方向，将访问过的节点给予已访问的标记，再将搜索到符合条件的所有节点进行相关的判断修改操作后，将符合搜索条件的节点入队
01 矩阵
解题思路
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
| class Solution {
public int[][] updateMatrix(int[][] mat) {
int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int m = mat.length;
int n = mat[0].length;
int[][] res = new int[m][n];
Queue<int[]> queue = new LinkedList<>();
boolean[][] finds = new boolean[m][n];
for(int i=0;i<mat.length;i++){
for(int j=0;j<mat[0].length;j++){
if(mat[i][j] == 0){
queue.offer(new int[]{i,j});
finds[i][j] = true;
}
}
}
while(!queue.isEmpty()){
int[] position = queue.poll();
int i = position[0],j = position[1];
for(int k=0;k<4;++k){
int ni = i + dirs[k][0];
int nj = j + dirs[k][1];
if(ni>=0 && ni<m && nj>=0 && nj<n && !finds[ni][nj]){
res[ni][nj] = res[i][j] + 1;
queue.offer(new int[]{ni,nj});
finds[ni][nj] = true;
}
}
}
return res;
}
}
|
994. 腐烂的橘子
解题思路
首先将所有的腐烂橘子的位置放入队列中，并且记录此时新鲜水果的数量与腐烂水果的数量，之后执行一次判断，若当前已经没有水果，直接返回0，否则开始腐烂的过程，腐烂的过程即是向腐烂水果的上下左右进行搜索，若发现新鲜的水果就将其腐蚀，由于本轮需要统计腐蚀水果的轮次，在出队时按照每轮放入的节点进行类似层序遍历的操作
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
| class Solution {
public int orangesRotting(int[][] grid) {
int[][] dirs = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
int m = grid.length, n=grid[0].length;
boolean[][] seen = new boolean[m][n];
Queue<int[]> queue = new LinkedList<>();
int numFresh = 0;
int numRotted = 0;
int step = 0;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(grid[i][j]==2){
numRotted++;
queue.offer(new int[]{i,j});
seen[i][j] = true;
}
if(grid[i][j]==1){
numFresh++;
}
}
}
if (numRotted == 0 && numFresh == 0) return 0;
while(!queue.isEmpty()){
step++;
int size = queue.size();
for(int num = 0;num<size;size--){
int[] pos = queue.poll();
int i = pos[0],j = pos[1];
for(int d=0;d<4;d++){
int ni = i + dirs[d][0];
int nj = j + dirs[d][1];
if(ni>=0 && ni<m && nj>=0 && nj<n && !seen[ni][nj]){
if(grid[ni][nj] == 1){
grid[ni][nj] = 2;
numFresh--;
queue.offer(new int[]{ni,nj});
}
seen[ni][nj] = true;
}
}
}
}
if(numFresh!=0){
return -1;
}else{
return step-1;
}
}
}
|