本节我们将继续汇总一些 LeetCode bfs与dfs相关的题。
地图分析
你现在手里有一份大小为 N x N 的「地图」（网格） grid，上面的每个「区域」（单元格）都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地，请你找出一个海洋区域，这个海洋区域到离它最近的陆地区域的距离是最大的。
我们这里说的距离是「曼哈顿距离」（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 这两个区域之间的距离是 |x0 - x1| + |y0 - y1| 。
如果我们的地图上只有陆地或者海洋，请返回 -1。
图片.png
bfs就完事了，从每个1的位置出发，其周围有0，赋值为1，该位置入队列，继续判断。
class Solution {
public:
int maxDistance(vector<vector<int>>& grid) {
int m=grid.size(),n=grid[0].size();
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});
}
}
}
if(q.size()==0 || q.size()==m*n){
return -1;
}
vector<vector<int>> dir{{1,0},{-1,0},{0,-1},{0,1}};
int level = -1;
while(!q.empty()){
int count = q.size();
while(count--){
auto cur =q.front();
q.pop();
for(int i=0;i<4;i++){
int x=cur.first+dir[i][0];
int y=cur.second+dir[i][1];
if(x>=0 && x<m && y>=0 && y<n && grid[x][y]==0){
grid[x][y]=1;
q.push({x,y});
}
}
}
level++;
}
return level;
}
};
01矩阵
给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。
两个相邻元素间的距离为 1 。
图片.png
如果要用bfs的话，这个题和上面那个题类似，需要增加一个额外的标注访问数组
class Solution {
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
vector<vector<int>> dir{{-1,0},{+1,0},{0,-1},{0,+1}};
int n=matrix.size(),m=matrix[0].size();
vector<vector<bool>> visted(n,vector<bool> (m,false));
vector<vector<int>> dist(n,vector<int> (m,0));
queue<pair<int,int>> q;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(matrix[i][j]==0){
q.push({i,j});
visted[i][j]=true;
}
}
}
while(!q.empty()){
auto now=q.front();
q.pop();
for(int i=0;i<4;i++){
int x=now.first+dir[i][0];
int y=now.second+dir[i][1];
if(x>=0&&x<n&&y>=0&&y<m&&!visted[x][y]){
visted[x][y]=true;
dist[x][y]=dist[now.first][now.second]+1;
q.push({x,y});
}
}
}
return dist;
}
};
这个题使用动态规划也是可以的，需要注意的是求解的顺序。
class Solution {
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
int n=matrix.size();
if(n==0){
return matrix;
}
int m=matrix[0].size();
vector<vector<int>> dist(n,vector<int>(m,INT_MAX/2));
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(matrix[i][j]==0){
dist[i][j]=0;
}else{
if(i>0){
dist[i][j]=min(dist[i][j],dist[i-1][j]+1);
}
if(j>0){
dist[i][j]=min(dist[i][j],dist[i][j-1]+1);
}
}
}
}
for(int i=n-1;i>=0;i--){
for(int j=m-1;j>=0;j--){
if(i<n-1){
dist[i][j]=min(dist[i][j],dist[i+1][j]+1);
}
if(j<m-1){
dist[i][j]=min(dist[i][j],dist[i][j+1]+1);
}
}
}
return dist;
}
};
机器人的运动范围
地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？
图片.png
这个也是一样的套路，只不过需要额外判断坐标。切不可直接遍历整个方格依次判断每个坐标，这样显然是不行的。
class Solution {
public:
int movingCount(int m, int n, int k) {
int res=1;
vector<vector<int>> grid(m,vector<int> (n,0));
vector<pair<int,int>> dir{{-1,0},{1,0},{0,-1},{0,1}};
queue<pair<int,int>> q;
q.push({0,0});
grid[0][0]=1;
while(!q.empty()){
auto point=q.front();
q.pop();
for(int i=0;i<4;i++){
int x=point.first+dir[i].first;
int y=point.second+dir[i].second;
if(0<=x&&x<=m-1&&0<=y&&y<=n-1){
if(fun(x)+fun(y)<=k&&grid[x][y]==0){
q.push({x,y});
grid[x][y]=1;
res++;
}
}
}
}
return res;
}
int fun(int num){
int tmp=0;
while(num){
tmp+=num%10;
num/=10;
}
return tmp;
}
};
