目录
1、图像渲染
题意简单说就是病毒扩散，感染数字相同且临近的数字
作者了解后发现，在类题目为floodfill算法，主要情况为将属性相同的同一个矩阵的一个范围内的元素进行操作
这个题目，作者的解法和刷题【2】里面的【黄金矿工】一样，迷宫找路，不过不用return后还原现场，作者最后返回的就是题目给的变量，只管深搜，不管恢复
class Solution {
//target是所有要感染的数字的值，扩散只能感染值为target的数
//color是要染成的新的值
int target;
int color;
//m是row,n是col
int m,n;
//dx，dy为方向向量
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
//防止走回头路
bool check[51][51];
public:
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int _color) {
m=image.size();
n=image[0].size();
target=image[sr][sc];
color=_color;
//有可能根本不用改，不要浪费时间，直接return
if(target==color)
{
return image;
}
image[sr][sc]=color;
check[sr][sc]=true;
dfs(image,sr,sc);
return image;
}
void dfs(vector<vector<int>>& image, int i,int j)
{
for(int p=0;p<4;p++)
{
int x=i+dx[p];
int y=j+dy[p];
if(x>=0&&x<m&&y>=0&&y<n&&!check[x][y]&&image[x][y]==target)
{
image[x][y]=color;
check[x][y]=true;
dfs(image,x,y);
//没有还原现场
}
}
}
};2、被围绕的区域
这个题比之前无脑dfs难一点，就是怎么处理这个边界问题，作者最初想着dfs统一对’O‘进行替换，在dfs内部用一个if做剪枝，一旦含有边界的数，就将改动的’O‘还原，然后这个消息用dfs的返回值进行返回（如搞一个bool的返回），但是发现这样会把边界的一块 'O'给拆散（因为return false，就不会再进行其他支路，意味着对联通块的遍历可能会在一遇到边界数就结束遍历，剩下一部分没有用check标记（这个check指的就是前面题目的标记量））
作者去看了一下其他解法：使用两个dfs，dfs1先对沾有边界的连通块进行标记，即dfs1不会对值进行更改，dfs2是处理剩下的’O‘,再次对board遍历，因为边界的块已经标记，不会再次出现，所以dfs2可以进行值的替换
class Solution {
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
//防止走回头路
bool check[201][201];
int m,n;
public:
void solve(vector<vector<char>>& board) {
m=board.size();
n=board[0].size();
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if((i==0||i==m-1||j==0||j==n-1)&&board[i][j]=='O'&&!check[i][j])
{
check[i][j]=true;
dfs1(board,i,j);
}
}
}
for(int i=0;i<m;i++)
{for(int j=0;j<n;j++)
{
if(board[i][j]=='O'&&!check[i][j])
{check[i][j]=true;
board[i][j]='X';
dfs2(board,i,j);
}
}
}
}
void dfs1(vector<vector<char>>& board,int i,int j)
{
for(int p=0;p<4;p++)
{
int x=i+dx[p];
int y=j+dy[p];
if(x>=0&&x<m&&y>=0&&y<n&&!check[x][y]&&board[x][y]=='O')
{
check[x][y]=true;
dfs1(board,x,y);
}
}
}
void dfs2(vector<vector<char>>& board,int i,int j)
{
for(int p=0;p<4;p++)
{
int x=i+dx[p];
int y=j+dy[p];
if(x>=0&&x<m&&y>=0&&y<n&&!check[x][y]&&board[x][y]=='O')
{
check[x][y]=true;
board[x][y]='X';
dfs2(board,x,y);
}
}
}
};class Solution {
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
//防止走回头路
bool check[201][201];
int m,n;
public:
void solve(vector<vector<char>>& board) {
m=board.size();
n=board[0].size();
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if((i==0||i==m-1||j==0||j==n-1)&&board[i][j]=='O'&&!check[i][j])
{
check[i][j]=true;
dfs1(board,i,j);
}
}
}
for(int i=0;i<m;i++)
{for(int j=0;j<n;j++)
{
if(board[i][j]=='O'&&!check[i][j])
{check[i][j]=true;
board[i][j]='X';
dfs2(board,i,j);
}
}
}
}
void dfs1(vector<vector<char>>& board,int i,int j)
{
for(int p=0;p<4;p++)
{
int x=i+dx[p];
int y=j+dy[p];
if(x>=0&&x<m&&y>=0&&y<n&&!check[x][y]&&board[x][y]=='O')
{
check[x][y]=true;
dfs1(board,x,y);
}
}
}
void dfs2(vector<vector<char>>& board,int i,int j)
{
for(int p=0;p<4;p++)
{
int x=i+dx[p];
int y=j+dy[p];
if(x>=0&&x<m&&y>=0&&y<n&&!check[x][y]&&board[x][y]=='O')
{
check[x][y]=true;
board[x][y]='X';
dfs2(board,x,y);
}
}
}
};3、太平洋大西洋水流问题
题目的意思就是找到坐标，水可以从这里流向两个海洋，（水从高到低，同时，相平的也可以流动）
1、解法一（暴力枚举）
class Solution {
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
bool check[201][201];
int m,n;
//是否触碰到P的边界，
//是否触碰到A的边界
bool is_P;
bool is_A;
public:
vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights)
{
m=heights.size();
n=heights[0].size();
vector<vector<int>> ret;
//对每个点都判断，即将每个点都当做山峰的顶点
//check与之前不一样，之前check遍历记录为true的不会在主函数力在遍历
//而这一题的思路是把check仅仅使用在深度遍历时，保证深度遍历步重复
//但面对新的【i】【j】,check是视为互不干扰的
//
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
check[i][j]=true;
if(i==0||j==0)
{
is_P=true;
}
if(i==m-1||j==n-1)
{
is_A=true;
}
dfs(heights,i,j);
//一旦以【i】【j】为顶点的路对应的变量is_p和is_A为true时意为着以该顶点可以触碰到两个海洋
if(is_A&&is_P)
{
ret.push_back({i,j});
}
is_A=is_P=false;
//check对每一个【i】【j】是一次性的
memset(check,0,sizeof(check));
}
}
return ret;
}
void dfs(vector<vector<int>>& heights,int i,int j)
{
for(int p=0;p<4;p++)
{
int x=i+dx[p];
int y=j+dy[p];
if(x>=0&&x<m&&y>=0&&y<n&&!check[x][y]&&heights[i][j]>=heights[x][y])
{
check[x][y]=true;
if(x==0||y==0)
{
is_P=true;
}
if(x==m-1||y==n-1)
{
is_A=true;
}
if(is_A&&is_P)
{
return ;
}
dfs(heights,x,y);
}
}
}
};2、解法二：逆向思考
题目要找到是扩散到达两个海的节点，反过来思考，两个海能够向上爬，并且相交，就是目标点
class Solution {
bool check_P[201][201];
bool check_A[201][201];
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
int m,n;
public:
vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights)
{
m=heights.size();
n=heights[0].size();
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(i==0||j==0)
{
check_P[i][j]=true;
dfs_P(heights,i,j);
}
if(i==m-1||j==n-1)
{
check_A[i][j]=true;
dfs_A(heights,i,j);
}
}
}
vector<vector<int>> ret;
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{if(check_A[i][j]&&check_P[i][j])
{
ret.push_back({i,j});
}
}
}
return ret;
}
void dfs_A(vector<vector<int>>& heights,int i,int j)
{
for(int p=0;p<4;p++)
{
int x=i+dx[p];
int y=j+dy[p];
if(x>=0&&x<m&&y>=0&&y<n&&!check_A[x][y]&&heights[i][j]<=heights[x][y])
{
check_A[x][y]=true;
dfs_A(heights,x,y);
}
}
}
void dfs_P(vector<vector<int>>& heights,int i,int j)
{
for(int p=0;p<4;p++)
{
int x=i+dx[p];
int y=j+dy[p];
if(x>=0&&x<m&&y>=0&&y<n&&!check_P[x][y]&&heights[i][j]<=heights[x][y])
{
check_P[x][y]=true;
dfs_P(heights,x,y);
}
}
}
};