之前我们用BFS解决floodfil算法
BFS 解决 FloodFill 算法_图像渲染_岛屿数量_被围绕的区域-CSDN博客
下面我们用dfs进行解决
733. 图像渲染
从初始位置开始dfs，找和它值相同的，并在dfs过程中把值改为目标值。因为会改变原数组，不用vis记录经过路径也可以。
边界情况：如果初始位置值结束目标值，那在dfs过程中不会改值，就会出现走重复路径的情况。遇到这种情况，其实是不用进行dfs，原数组就是最终结果。
class Solution {
vector<int> dx={1,-1,0,0};
vector<int> dy={0,0,1,-1};
int m,n;
int prev,color;
public:
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int _color)
{
//1.记录要修改的像素值
prev=image[sr][sc];color=_color;
//2.处理边界情况 （第一个就是要变成的颜色，就没必要处理）
if(prev==color) return image;
//3.二维数组边界 m行数 n列数
m=image.size(),n=image[0].size();
dfs(image,sr,sc);
return image;
}
void dfs(vector<vector<int>>& image, int i, int j)
{
//进入dfs就更改值
image[i][j]=color;
for(int k=0;k<4;k++)
{
int x=i+dx[k],y=j+dy[k];
if(x>=0&&x<m&&y>=0&&y<n&&image[x][y]==prev)
{
dfs(image,x,y);
}
}
return;
}
};200. 岛屿数量
class Solution {
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
bool vis[301][301];
int m,n;
public:
int numIslands(vector<vector<char>>& grid) {
int re=0;
m=grid.size(),n=grid[0].size();
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(grid[i][j]=='1'&&!vis[i][j])
{
dfs(grid,i,j); re++;
}
}
}
return re;
}
void dfs(vector<vector<char>>& grid,int i,int j)
{
vis[i][j]=true;
for(int k=0;k<4;k++)
{
int x=i+dx[k],y=j+dy[k];
if(x>=0&&x<m&&y>=0&&y<n&&!vis[x][y]&&grid[x][y]=='1')
{
dfs(grid,x,y);
}
}
return;
}
};695. 岛屿的最大面积
每遍历到一个1且没有标记过，就从该位置进行dfs,进入dfs就标记并记录当前面积，dfs结束获取这一块1的面积。
class Solution {
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int m,n;
bool vis[51][51];
//记录“1”块的面积
int count=0;
public:
int maxAreaOfIsland(vector<vector<int>>& grid) {
m=grid.size(),n=grid[0].size();
int re=0;
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(!vis[i][j]&&grid[i][j]==1)
{
count=0;
dfs(grid,i,j);
re=max(re,count);
}
}
}
return re;
}
int dfs(vector<vector<int>>& grid,int i,int j)
{
//进入一个面积+1 标记
count++;
vis[i][j]=true;
for(int k=0;k<4;k++)
{
int x=i+dx[k],y=j+dy[k];
if(x>=0&&x<m&&y>=0&&y<n&&!vis[x][y]&&grid[x][y]==1)
{
dfs(grid,x,y);
}
}
return count;
}
};130. 被围绕的区域
class Solution {
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
bool vis[201][201];
int m, n;
public:
void solve(vector<vector<char>>& board) {
m = board.size(), n = board[0].size();
// 1. 先处理边界上的 'O' 联通块 对应的vis改为1
for (int j = 0; j < n; j++) {
if (board[0][j] == 'O')
dfs(board, 0, j);
if (board[m - 1][j] == 'O'&&!vis[m-1][j])
dfs(board, m - 1, j);
}
for (int i = 0; i < m; i++) {
if (board[i][0] == 'O'&&!vis[i][0])
dfs(board, i, 0);
if (board[i][n - 1] == 'O'&&!vis[i][n-1])
dfs(board, i, n - 1);
}
// 2. 更改
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (board[i][j] == 'O'&&!vis[i][j])
board[i][j] = 'X';
}
void dfs(vector<vector<char>>& board, int i, int j)
{
vis[i][j]=true;
for(int k=0;k<4;k++)
{
int x=i+dx[k],y=j+dy[k];
if(x >= 0 && x < m && y >= 0 && y < n &&!vis[x][y]&&board[x][y]=='O')
{
dfs(board,x,y);
}
}
return;
}
};417. 太平洋大西洋水流问题
每个格子上都有水，水从高处流向低处，问那个格子的水可以流向太平洋和大西洋。
思路一：对每个格子都进行dfs，找可以流向两个洋的格子。
时间复杂度太高，不推荐
class Solution {
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
vector<vector<int>> re;
bool vis[201][201];
bool P=false,A=false;
int m,n;
public:
vector<vector<int>> pacificAtlantic(vector<vector<int>>& h) {
m=h.size(),n=h[0].size();
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
P=false,A=false;
vis[i][j]=true;
dfs(h,i,j);
vis[i][j]=false;
if(P&&A) re.push_back({i,j});
}
}
return re;
}
void dfs(vector<vector<int>>& h,int i,int j)
{
if(i==m-1||j==n-1)
A=true;
if(i==0||j==0)
P=true;
if(A&&P) return;
for(int k=0;k<4;k++)
{
int x=i+dx[k],y=j+dy[k];
if(x>=0&&x<m&&y>=0&&y<n&&!vis[x][y]&&h[x][y]<=h[i][j])
{
vis[x][y]=true;
dfs(h,x,y);
vis[x][y]=false;
}
}
return;
}
};方法二：正难则反
水从高到低，反过来水从低到高，路径是一样的。
1.看临边是Pac洋的格子从低到高走，四周的格子比它大就可以走。(用绿色标记走过的格子)
2.看临边是Atl洋的格子从低到高走，四周的格子比它大就可以走。(用红色标记走过的格子)
它们相交的格子就是可以流向两个洋的格子
因为有两种标记，vis图要有两个。对靠近Pac洋的格子dfs进行标记，还要对靠近Atl洋的格子dfs进行标记。两个vis图都为true的位置为目标位置。
注意：vis1 vis2要定义成全局变量 进行传参 保存改变结果
或者在函数内定义成vector<vector<bool> vis(m,vector<bool>(n))；进行引用&传参
class Solution {
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
vector<vector<int>> re;
bool vis1[201][201];
bool vis2[201][201];
int m, n;
public:
vector<vector<int>> pacificAtlantic(vector<vector<int>>& h) {
m = h.size();
n = h[0].size();
// // 初始化访问数组
// memset(vis1, false, sizeof(vis1));
// memset(vis2, false, sizeof(vis2));
// 从每个边缘开始 DFS
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (i == 0 || j == 0) // 太平洋
dfs(h, i, j, vis1);
if (i == m - 1 || j == n - 1) // 大西洋
dfs(h, i, j, vis2);
}
}
// 收集同时到达太平洋和大西洋的坐标
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (vis1[i][j] && vis2[i][j])
re.push_back({i, j});
}
}
return re;
}
void dfs(vector<vector<int>>& h, int i, int j, bool vis[201][201])
{
vis[i][j] = true;
for (int k = 0; k < 4; k++)
{
int x = i + dx[k], y = j + dy[k];
if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && h[x][y] >=h[i][j])
{
dfs(h, x, y, vis);
}
}
}
};
529. 扫雷游戏
在eg1中click位置点击，该格四周没有地雷，改为B，并向四周dfs找E未挖出的格子。如果该格周围有地雷就改为周围地雷数，不进行dfs。
点到地雷就更改并返回。
我们可以先用map数组记录每个格子四周有多少地雷，这样在判断该格四周是否有地雷就不用遍历周围 直接看map中是否有数就行。
class Solution {
int map[51][51]={0};
int dx[8]={1,-1,0,0,1,-1,1,-1};
int dy[8]={0,0,1,-1,-1,1,1,-1};
int m,n;
public:
vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
m=board.size(),n=board[0].size();
//在map图中记录该格周围有多少地雷
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
{
if(board[i][j]=='M')
{
for(int k=0;k<8;k++)
{
int x=i+dx[k],y=j+dy[k];
if(x >= 0 && x < m && y >= 0 && y < n ) map[x][y]++;
}
}
}
int x=click[0],y=click[1];
//遇到地雷更改并返回
if(board[x][y]=='M')
{
board[x][y]='X';
return board;
}
//遇到E分两情况 四周有地雷和无地雷
else
{
dfs(board,x,y);
}
return board;
}
void dfs(vector<vector<char>>& board,int i,int j)
{
//1.周围有地雷 E变为周围地雷数
if(map[i][j]) board[i][j]='0'+map[i][j];
//2.没有地雷 E变B并以该各为起点dfs找E未挖出的格
else
{
board[i][j]='B';
for(int k=0;k<8;k++)
{
int x=i+dx[k],y=j+dy[k];
if(x >= 0 && x < m && y >= 0 && y < n &&board[x][y]=='E')
{
dfs(board,x,y);
}
}
}
return;
}
};LCR 130. 衣橱整理
从(0,0)进行dfs遍历所有格子，找出符合条件的格子。不能重复记录符合条件的格子，用vis记录走过的路径。
class Solution {
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
bool vis[101][101];
int m,n,cnt;
int re=0;
public:
int wardrobeFinishing(int _m, int _n, int _cnt) {
m=_m,n=_n,cnt=_cnt;
dfs(0,0);
return re;
}
void dfs(int i,int j)
{
vis[i][j]=true;
int tmp1=i,tmp2=j,sum=0;
while(tmp1||tmp2)
{
sum+=tmp1%10;
tmp1/=10;
sum+=tmp2%10;
tmp2/=10;
}
if(sum>cnt) return;
else re++;
for(int k=0;k<4;k++)
{
int x=i+dx[k],y=j+dy[k];
if(x>=0&&x<m&&y>=0&&y<n&&!vis[x][y])
{
dfs(x,y);
}
}
return;
}
};
