浙江 外贸网站建设,网站建设推广选哪家,农产品跨境电商平台有哪些,腾讯云建站平台floodfill#xff0c;翻译为洪水灌溉#xff0c;而floodfill算法本质上是为了解决在矩阵中性质相同的联通块问题。
一、图像渲染
. - 力扣#xff08;LeetCode#xff09; class Solution {
public:int dx[4]{0,0,1,-1};int dy[4]{1,-1,0,0};int prev;//记住初始值int m,… floodfill翻译为洪水灌溉而floodfill算法本质上是为了解决在矩阵中性质相同的联通块问题。
一、图像渲染
. - 力扣LeetCode class Solution {
public:int dx[4]{0,0,1,-1};int dy[4]{1,-1,0,0};int prev;//记住初始值int m,n;vectorvectorint floodFill(vectorvectorint image, int sr, int sc, int color) {//先考虑边界条件如果对应位置和color是一样的那么直接返回if(image[sr][sc]color) return image;mimage.size(),nimage[0].size();previmage[sr][sc];dfs(image,sr,sc,color); return image;}void dfs(vectorvectorint image, int i, int j, int color) //直接用引用在矩阵上修改{//第一步将当前位置修改成colorimage[i][j]color;//第二步用向量定义四个方向然后去找for(int k0;k4;k){int xidx[k],yjdy[k];if(x0xmy0ynimage[x][y]prev)dfs(image,x,y,color);}}
}; 二、岛屿问题
. - 力扣LeetCode class Solution {
public:int ret0;bool check[300][300];int m,n;int numIslands(vectorvectorchar grid) {mgrid.size(),ngrid[0].size();for(int i0;im;i)for(int j0;jn;j){if(!check[i][j]grid[i][j]1)//该数没被选过并且为1{ret;//说明找到一块岛屿dfs(grid,i,j);//然后让dfs去相邻位置将对应的子块给标记成true} }return ret;}int dx[4]{0,0,1,-1};int dy[4]{1,-1,0,0};void dfs(vectorvectorchar grid,int i,int j){//首先先把当前位置标记成选过check[i][j]true;//然后通过向量去其他位置找for(int k0;k4;k){int xidx[k],yjdy[k];if(x0xmy0yn!check[x][y]grid[x][y]1)dfs(grid,x,y);//继续去下一个位置找}}
};
三、岛屿的最大面积
. - 力扣LeetCode class Solution {
public:bool check[50][50];int m,n;int count;//数每个字块的岛屿数量int dx[4]{0,0,1,-1};int dy[4]{1,-1,0,0};int maxAreaOfIsland(vectorvectorint grid) {mgrid.size(),ngrid[0].size();int ret0;for(int i0;im;i)for(int j0;jn;j)if(!check[i][j]grid[i][j]1){count0;//重置countdfs(grid,i,j);retmax(ret,count);}return ret;}void dfs(vectorvectorint grid,int i,int j){count;check[i][j]true;for(int k0;k4;k){int xidx[k],yjdy[k];if(x0xmy0yn!check[x][y]grid[x][y]1){dfs(grid,x,y);}}}
};
四、被围绕的区域
. - 力扣LeetCode class Solution {
public://正难则反先去找边界//1先找到边界的o然后用dfs去找 找到了就修改成.//2此时矩阵里的o肯定是在区域内的了直接遍历一遍矩阵修改即可顺便把.修改成圈int m,n;void solve(vectorvectorchar board) {mboard.size(),nboard[0].size();//先处理第一行的最后一行for(int j0;jn;j){if(board[0][j]O) dfs(board,0,j);if(board[m-1][j]O) dfs(board,m-1,j);}//处理第一列和第二列for(int i0;im;i){if(board[i][0]O)dfs(board,i,0);if(board[i][n-1]O) dfs(board,i,n-1);}//此时剩下位置的O给他改成X然后.复原成Ofor(int i0;im;i)for(int j0;jn;j){if(board[i][j].) board[i][j]O;else if(board[i][j]O) board[i][j]X;}}int dx[4]{0,0,1,-1};int dy[4]{1,-1,0,0};void dfs(vectorvectorchar board,int i,int j){//先将当前位置改成.board[i][j].;for(int k0;k4;k){int xidx[k],yjdy[k];if(x0xmy0ynboard[x][y]O) dfs(board,x,y);}}
};
五、太平洋大西洋水流问题
. - 力扣LeetCode class Solution {
public://思路正难则反用两个标记数组去标记两个大洋的位置int m,n;vectorvectorint ret;//记录返回值int dx[4]{0,0,1,-1};int dy[4]{1,-1,0,0};vectorvectorint pacificAtlantic(vectorvectorint h) {mh.size(),nh[0].size();//设置两个标记数组vectorvectorbool pac(m,vectorbool(n));auto atlpac;//先去找pacfor(int j0;jn;j) dfs(h,0,j,pac);for(int i0;im;i) dfs(h,i,0,pac);//再去找atlfor(int j0;jn;j) dfs(h,m-1,j,atl);for(int i0;im;i) dfs(h,i,n-1,atl);//然后根据两个标记数组去记录下标for(int i0;im;i)for(int j0;jn;j)if(pac[i][j]atl[i][j])//如果坐标同时被两个数组标记了就统计最终的结果ret.push_back({i,j});return ret;}void dfs(vectorvectorint h,int i,int j, vectorvectorboolvis){//先将该点设置为选过vis[i][j]true;//定义四个方向然后去找for(int k0;k4;k){int xidx[k],yjdy[k];if(x0xmy0yn!vis[x][y]h[x][y]h[i][j])dfs(h,x,y,vis);}}
};
六、扫雷游戏
. - 力扣LeetCode class Solution {
public:int dx[8]{0,0,1,-1,1,1,-1,-1};int dy[8]{1,-1,0,0,1,-1,1,-1}; //周围的八个方向int m,n;vectorvectorchar updateBoard(vectorvectorchar board, vectorint click) {mboard.size(),nboard[0].size();//考虑边界情况如果是雷直接返回int xclick[0],yclick[1];if(board[x][y]M) {board[x][y]X;}else//说明不是雷dfs去判断该位置的情况{dfs(board,x,y);}return board;}void dfs(vectorvectorchar board,int i,int j){//进行搜索int count0;//用来数雷for(int k0;k8;k){int xidx[k],yjdy[k];if(x0xmy0ynboard[x][y]M) count;}if(count) board[i][j]0count;else //没有雷就继续去展开{board[i][j]B;for(int k0;k8;k){int xidx[k],yjdy[k];if(x0xmy0ynboard[x][y]E) dfs(board,x,y);}}}
};
七、衣柜整理
. - 力扣LeetCode class Solution {
public:bool vis[100][100];int m,n,cnt;int ret;int wardrobeFinishing(int _m, int _n, int _cnt) {m_m,n_n,cnt_cnt;ret0;//统计符合要求的各自的数目dfs(0,0);return ret;}void dfs(int i,int j){ ret;vis[i][j]true;if(j1ncheck(i,j1)!vis[i][j1]) dfs(i,j1);//向右找if(i1mcheck(i1,j)!vis[i1][j]) dfs(i1,j);//向下找}bool check(int i,int j){int temp0;while(i){temp(i%10);i/10;}while(j){temp(j%10);j/10;}return tempcnt;}
};
