【刷题23】多源BFS
目录
- 一、01矩阵
- 二、飞地的数量
- 三、地图中的最高点
- 四、地图分析
一、01矩阵
题目：
思路：
- 找1与最近的0的距离，正难则反，先找0，再去找1，0与1的最短距离
- 矩阵中所有的0入队列
- 一层一层的往外扩展，没越界、是1，没经过的元素就被赋值为当前的层数
代码：
class Solution {
public:
int bx[4] = {-1,1,0,0};
int by[4] = {0,0,-1,1};
vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
int n = mat.size();
int m = mat[0].size();
queue<pair<int, int>> q;
vector<vector<bool>> vis(n, vector<bool>(m, false));
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
if(mat[i][j] == 0)
{
q.push({i, j});
vis[i][j] = true;
}
}
}
int step = 0;
while(!q.empty())
{
int k = q.size();
step++;// 层数
while(k--)
{
int x1 = q.front().first;
int y1 = q.front().second;
q.pop();// 删除队头元素
for(int i=0; i<4; i++)
{
int x2 = x1+bx[i];
int y2 = y1+by[i];
if(x2>=0&&x2<n&&y2>=0&&y2<m&&mat[x2][y2]==1&&!vis[x2][y2])
{
q.push({x2, y2});// 入队列
mat[x2][y2] = step;// 距离
vis[x2][y2] = true;// 已经过
}
}
}
}
return mat;
}
};
二、飞地的数量
题目：
思路：
- 找边界的1，放入队列，标记为true；同时ret统计矩阵中所有1的个数
- 统计count可以到达边界的1的个数，初始化为队列的元素个数，即边界的1
- 返回值为ret-count
代码：
class Solution {
public:
int bx[4] = {-1,1,0,0};
int by[4] = {0,0,-1,1};
int numEnclaves(vector<vector<int>>& grid) {
int n = grid.size();
int m = grid[0].size();
vector<vector<bool>> vis(n, vector<bool>(m, false));
queue<pair<int,int>> q;
int ret = 0;// 所有1的数量
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
if(grid[i][j] == 1)
ret++;
if(i == 0 || i == n-1 || j == 0 || j == m-1)
{
if(grid[i][j] == 1)
{
q.push({i, j});
vis[i][j] = true;
}
}
}
}
//
int count = q.size();// 都可以到边界的1数量
while(!q.empty())
{
int k = q.size();
while(k--)
{
int x1 = q.front().first;
int y1 = q.front().second;
q.pop();
for(int i=0; i<4; i++)
{
int x2 = x1+bx[i];
int y2 = y1+by[i];
if(x2>=0&&x2<n&&y2>=0&&y2<m&&grid[x2][y2]==1&&!vis[x2][y2])
{
q.push({x2, y2});
vis[x2][y2] = true;
count++;
}
}
}
}
return ret-count;
}
};
三、地图中的最高点
题目：
注意：
- 矩阵中，1是水域，0是陆地
- 要求：将所有水域的高度变成0（就是水域格子置0），然后以水域格子为中心（可能有多个水域），上下左右扩展，高度差至多为1，最终将安排高度后的矩阵返回
思路：多源BFS
- 与01矩阵的思路一样，前面找1（水域）找到后，把1变成0，然后后面全都一样
代码：
class Solution {
public:
int bx[4] = {-1,1,0,0};
int by[4] = {0,0,-1,1};
vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {
int n = isWater.size();
int m = isWater[0].size();
vector<vector<bool>> vis(n, vector<bool>(m, false));
queue<pair<int, int>> q;
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
if(isWater[i][j] == 1)
{
q.push({i, j});
isWater[i][j] = 0;// 1变成0--高度
vis[i][j] = true;
}
}
}
//
int step = 0;
while(!q.empty())
{
int k = q.size();
step++;
while(k--)
{
int x1 = q.front().first;
int y1 = q.front().second;
q.pop();
for(int i=0; i<4; i++)
{
int x2 = x1+bx[i];
int y2 = y1+by[i];
if(x2>=0&&x2<n&&y2>=0&&y2<m&&isWater[x2][y2]==0&&!vis[x2][y2])
{
q.push({x2, y2});
isWater[x2][y2] = step;
vis[x2][y2] = true;
}
}
}
}
return isWater;
}
};
四、地图分析
题目：
思路：
- 正难则反，把问题转换为=》陆地找海洋
- 其他与前面同
- 注意都是海洋或者都是陆地的情况
代码：
class Solution {
public:
int bx[4] = {-1,1,0,0};
int by[4] = {0,0,-1,1};
int maxDistance(vector<vector<int>>& grid) {
int n = grid.size();
int m = grid[0].size();
vector<vector<bool>> vis(n, vector<bool>(m, false));
queue<pair<int, int>> q;
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
if(grid[i][j] == 1)
{
q.push({i, j});
vis[i][j] = true;
}
}
}
//
if(q.size() == 0) return -1;// 只有海洋
if(q.size() == n*m) return -1;// 只有陆地
int step = 0;
while(!q.empty())
{
int k = q.size();
step++;
while(k--)
{
int x1 = q.front().first;
int y1 = q.front().second;
q.pop();
for(int i=0; i<4; i++)
{
int x2 = x1+bx[i];
int y2 = y1+by[i];
if(x2>=0&&x2<n&&y2>=0&&y2<m&&grid[x2][y2]==0&&!vis[x2][y2])
{
q.push({x2, y2});
vis[x2][y2] = true;
grid[x2][y2] = step;
}
}
}
}
int ret = 0;
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
ret = max(ret, grid[i][j]);
}
}
return ret;
}
};