【BFS/DFS 解决 FloodFill 算法】被围绕的区域

文章目录题目解析方向向量BFS广度优先搜索算法原理防止重复访问全局变量层序遍历代码实现DFS深度优先搜索算法原理全局变量dfs 函数函数头函数体代码实现题目链接130. 被围绕的区域题目解析首先介绍一下什么是FloodFill算法FloodFill算法也称为洪水填充算法指的是在区域中找到性质相同的联通块注意这里的联通块指的是上下左右相邻斜线不能算做相邻。该算法可以使用深度优先搜索和广度优先搜索来解决。题目给出一个m x n的矩阵board由若干个字符X和O组成。在矩阵中由O单元格相互连接水平或者垂直方向相邻组成的称为区域若区域中的所有O单元格都不在矩阵边缘则该区域被包围。我们需要捕获所有被围绕的区域并且将这些区域单元格中的O改为X在原矩阵上修改。例如X X X XX O O XX X O XX O X XX X X XX X X XX X X XX O X X方向向量在继续之前有必要知道我们在解决矩阵搜索类问题时访问某位置上下左右四个方向的操作。坐标〖i, j〗的上下左右四个坐标是在i和j加上了 0、1、-1 上下坐标〖i (-1), j 0〗和〖i 1, j 0〗左右坐标〖i 0, j (-1)〗和〖i 0, j 1〗。因此需要定义两个向量坐标dx {0, 0, -1, 1}dy {-1, 1, 0, 0}。在需要访问时通过 〖row, col〗坐标和四次循环依次访问即可。BFS广度优先搜索算法原理思路直接遍历矩阵找到被包围的O就将其修改为X并且通过 BFS 将与该方格相连的所有O都找到并修改但是❗这种方法会将边缘的O及其连通块一起修改这不符合题目的要求。我们可以先将边缘的O改为其他字符如.这样就不会被修改了到时候再将其修改回O即可。思路如下先扫描四个边界找到一个在边缘的O就修改为.并通过 BFS 找到与其相连的连通块并修改四个边界扫描完毕后遍历矩阵找到被包围的O就将其修改为X若找到.则将其改回O防止重复访问我们在进行 BFS 的时候可能会重复进入某个方格。可以用两种方式避免重复访问在原数组上修改使用标记数组本题目使用第一种方式因为题目明确说明我们可以在原数组上修改若是面试场景需要确认能否在原数组上修改所以我们可以利用这一点巧妙地防止某个位置被重复访问。全局变量我们需要用到矩阵的行数和列数因此将m和n作为全局变量方向数组dx和dy辅助我们从某个位置向其上下左右四个方向访问。intm,n;int[]dx{0,0,-1,1};int[]dy{-1,1,0,0};由于本题可以直接在数组上修改已经达到不重复访问某位置的目的因此不再需要布尔标记数组了。层序遍历我们使用一个队列实现层序遍历的操作队列存储与〖row, col〗位置相连的O方格坐标当队列不为空时一直取出队首元素获取坐标然后根据坐标向该元素的上下左右四个方向访问查找符合条件的O方格与该位置相连找到符合条件的O方格之后入队然后将该位置的值改为.当队列为空层序遍历完毕由于我们每次扫描矩阵边界找到一个O方格时都要进行一次层序遍历操作因此将该操作封装为一个方法。代码实现classSolution{intm,n;// 矩阵board的行数和列数// 辅助访问某一位置上下左右方向的数组int[]dx{0,0,-1,1};int[]dy{-1,1,0,0};publicvoidsolve(char[][]board){// 初始化mboard.length;nboard[0].length;// 1.先扫描边界的O将其修改为.// 通过bfs将与其相连的所有O也修改为.for(intj0;jn;j){if(board[0][j]O){bfs(board,0,j);}if(board[m-1][j]O){bfs(board,m-1,j);}}for(inti0;im;i){if(board[i][0]O){bfs(board,i,0);}if(board[i][n-1]O){bfs(board,i,n-1);}}// 2.遍历矩阵找到被包围的O并修改为X同时将边界.修改为Ofor(inti0;im;i){for(intj0;jn;j){if(board[i][j]O){board[i][j]X;}if(board[i][j].){board[i][j]O;}}}}publicvoidbfs(char[][]board,introw,intcol){board[row][col].;// 将位置[row,col]修改为.// 使用队列存储与[row,col]位置相连的坐标Queueint[]queuenewArrayDeque();queue.offer(newint[]{row,col});// 层序遍历while(!queue.isEmpty()){int[]topqueue.poll();// 取出队首元素rowtop[0];coltop[1];// 获取队首元素的坐标// 从队首元素向上下左右四个方向访问与其相连的O并修改for(intk0;k4;k){intxrowdx[k],ycoldy[k];if(x0xmy0yn){if(board[x][y]O){queue.offer(newint[]{x,y});// 入队board[x][y].;// 将该位置的值改为.}}}}}}DFS深度优先搜索算法原理我们采用深度优先遍历的思路遍历矩阵找到在矩阵内部被包围的O将其修改为X但是这道题目如果直接沿用之前的解法你会发现边缘单元格的O也会被修改成X导致出错。所以我们要先考虑边缘单元格的O对其做个标记防止被修改。大致的过程如下先对边缘单元格的O进行处理将其修改为.以防止后续遍历矩阵时连同被包围的区域一起被修改遍历矩阵找到O此时一定是被包围的区域不可能是边缘单元格将其修改为X找到.将其修改为O全局变量将题目所给矩阵grid改为全局变量以便递归m和n表示矩阵的大小方向数组dx和dy辅助我们访问某一个位置的上下左右四个方位。char[][]board;intm,n;int[]dx{0,0,-1,1};int[]dy{-1,1,0,0};dfs 函数函数头我们这次给 dfs 函数设置的任务是将某一指定位置及其上下左右四个方位的值改为.即处理边缘单元格。因此参数是某位置的坐标 〖row, col〗无返回值。dfs(introw,intcol);函数体我们进入函数的第一个操作是先将位置〖row, col〗的值改为.然后往上下左右进行深度优先遍历。代码实现classSolution{char[][]board;intm,n;int[]dx{0,0,-1,1};int[]dy{-1,1,0,0};publicvoidsolve(char[][]givenBoard){boardgivenBoard;mboard.length;nboard[0].length;// 1.先扫描边界遇到O就修改成.// 并通过dfs将与其相连的所有O都修改for(intj0;jn;j){if(board[0][j]O){dfs(0,j);}if(board[m-1][j]O){dfs(m-1,j);}}for(inti0;im;i){if(board[i][0]O){dfs(i,0);}if(board[i][n-1]O){dfs(i,n-1);}}// 2.找到被包围的O就修改为X同时将边缘的.改为Ofor(inti0;im;i){for(intj0;jn;j){if(board[i][j]O){board[i][j]X;}if(board[i][j].){board[i][j]O;}}}}publicvoiddfs(introw,intcol){board[row][col].;for(intk0;k4;k){intxrowdx[k],ycoldy[k];if(x0xmy0yn){if(board[x][y]O){dfs(x,y);//找到与该位置相连的O}}}}}完