目录
01矩阵
飞地的数量
地图中的最高点
地图分析
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;}
};
