目录
01矩阵
题目
思路
解决这道题使用的方法是多源BFS，多源BFS区别于单源BFS的地方在于起点不是一个多个，首先将矩阵中所有的0加入队列中，创建一个和原始矩阵大小相同的矩阵dists，矩阵dists中的值为每个点距离0的最短距离，然后进行宽度优先遍历，将没有遍历过的点添加到队列中，并更新该点到0的最短距离，最后返回dists矩阵就可以了。
代码
class Solution {
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
int m=mat.size(),n=mat[0].size();
vector<vector<int>> dists(m,vector<int>(n,-1));
queue<pair<int,int>> q;
for(int i=0;i<m;i++)
for(int j=0;j<n;j++){
if(mat[i][j]==0){
q.push({i,j});
dists[i][j]=0;
}
}
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
while(!q.empty()){
int sz=q.size();
while(sz--){
auto [a,b]=q.front();
q.pop();
for(int k=0;k<4;k++){
int x=a+dx[k],y=b+dy[k];
if(x>=0 && x<m && y>=0 && y<n && dists[x][y]==-1){
q.push({x,y});
dists[x][y]=dists[a][b]+1;
}
}
}
}
return dists;
}
};飞地的数量
题目
思路
解决这道题使用的方法是多源BFS，多源BFS区别于单源BFS的地方在于起点不是一个多个。
我们可能想到遍历二维矩阵中的每一个点，对该点进行DFS或者BFS，但是这样的话有点麻烦，我们不妨采用“正难则反”的思想，将二维矩阵中四周值为1的点加入队列中，然后进行宽度优先遍历，将没有访问过的且值为1的点加入队列中。
最后，遍历二维矩阵中所有的点，如果该位置值为1且没有被访问过，那么这个位置就是一个飞地，统计所有的飞地的数量，返回即可。
代码
class Solution {
public:
int numEnclaves(vector<vector<int>>& grid) {
int m=grid.size(),n=grid[0].size();
vector<vector<bool>> vis(m,vector<bool>(n));
queue<pair<int,int>> q;
for(int i=0;i<m;i++){
if(grid[i][0]==1) q.push({i,0}),vis[i][0]=true;
if(grid[i][n-1]==1) q.push({i,n-1}),vis[i][n-1]=true;;
}
for(int i=0;i<n;i++){
if(grid[0][i]==1) q.push({0,i}),vis[0][i]=true;;
if(grid[m-1][i]==1) q.push({m-1,i}),vis[m-1][i]=true;;
}
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
while(!q.empty()){
int sz=q.size();
while(sz--){
auto [a,b]=q.front();
q.pop();
for(int i=0;i<4;i++){
int x=a+dx[i],y=b+dy[i];
if(x>=0 && x<m && y>=0 && y<n && grid[x][y] && !vis[x][y])
q.push({x,y}),vis[x][y]=true;
}
}
}
int ret=0;
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
if(grid[i][j]==1 && vis[i][j]==false)
ret++;
return ret;
}
};地图中的最高点
题目
思路
解决这道题使用的方法是多源BFS，多源BFS区别于单源BFS的地方在于起点不是一个多个。
首先，我们创建一个和原始矩阵大小相同的二维矩阵heights，然后扫描整个二维矩阵，将所有值为1的点加入队列中，然后进行BFS，将没有访问过的点加入队列中，并更新该位置的高度值，最后，返回二维矩阵heighgts就可以了。
代码
class Solution {
public:
vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {
int m=isWater.size(),n=isWater[0].size();
vector<vector<int>> heights(m,vector<int>(n,-1));
queue<pair<int,int>> q;
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
if(isWater[i][j]==1)
q.push({i,j}),heights[i][j]=0;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
while(!q.empty()){
int sz=q.size();
while(sz--){
auto [a,b]=q.front();
q.pop();
for(int k=0;k<4;k++){
int x=a+dx[k],y=b+dy[k];
if(x>=0 && x<m && y>=0 && y<n && isWater[x][y]==0 && heights[x][y]==-1)
q.push({x,y}),heights[x][y]=heights[a][b]+1;
}
}
}
return heights;
}
};地图分析
题目
思路
解决这道题使用的方法是多源BFS，多源BFS区别于单源BFS的地方在于起点不是一个多个。
我们可能会想到对矩阵中所有值为0的点进行BFS，找出所有距离陆地的距离中的最大距离，但是这样有点麻烦，我们不妨对矩阵中所有值为1的点进行BFS，如果队列的大小为n*n或者为0，说明只存在陆地或者只存在海洋，返回-1即可；否则，创建一个和原始矩阵大小相同的二维矩阵dists，然后将没有访问过的点添加到队列中，并更新该位置到陆地的距离，最后返回dists矩阵中的最大值即可。
代码
class Solution {
public:
int maxDistance(vector<vector<int>>& grid) {
int n=grid.size();
vector<vector<int>> dists(n,vector<int>(n,-1));
queue<pair<int,int>> q;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
if(grid[i][j]==1)
q.push({i,j}),dists[i][j]=0;
if(q.size()==n*n || q.size()==0)
return -1;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
while(!q.empty()){
int sz=q.size();
while(sz--){
auto [a,b]=q.front();
q.pop();
for(int k=0;k<4;k++){
int x=a+dx[k],y=b+dy[k];
if(x>=0 && x<n && y>=0 && y<n && dists[x][y]==-1)
q.push({x,y}),dists[x][y]=dists[a][b]+1;
}
}
}
int ret=0;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
ret=max(ret,dists[i][j]);
return ret;
}
};