给你一个 m x n 的矩阵 board ,由若干字符 ‘X’ 和 ‘O’ ,找到所有被 ‘X’ 围绕的区域,并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。
示例1
输入:board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]] 输出:[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]] 解释:被围绕的区间不会存在于边界上,换句话说,任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上,或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。 如果两个元素在水平或垂直方向相邻,则称它们是“相连”的
示例2
输入:board = [["X"]] 输出:[["X"]]
首先抓住题干重要信息“任何边界上的 ‘O’ 都不会被填充为 ‘X’”,这就说明任何与边界相连的’O’同样也是不会被填充的,并且这里我们还要注意题目中说“如果两个元素在水平或垂直方向相邻,则称它们是“相连”的“,就表示元素对角线上的元素我们是不需要管的,即使相连也不能算作连通。
然后我们来看一下这道题的做法,‘O’区域有两种,一种是与边界相连,不改变的,一种是与边界不相连,需要填充为‘X’的。
1.与边界相连的‘O’,我们需要在搜索的时候对它进行一个标记,或者是把它填充成另一个字母作为一个标记,然后在最后遍历一遍的时候将它复原。
2.与边界不相连的’O’,我们在搜索的时候可以直接忽略它,因为我们的搜索目标其实只是与边界相连的‘O’,其他’O’会在最后遍历一遍的时候直接填充为‘X’。
思路大致有了,dfs应该如何去写呢,首先我们要清楚我们的搜索起点,搜索起点是这个mxn矩阵的最外围一圈的所有元素,因为我们要搜索与边界的’O’相连的‘O’,如果边界不是’O‘,我们可以直接跳过当前边界,不搜索,然后在进入dfs后,我们对当前搜索到的点的上下左右方向的点进行搜索,一直到搜索到的点为’X‘为止,这里就是递归搜索了。
dfs的写法:
先写好dfs的出口,我们在搜索到什么时候就要终止dfs呢
1.当dfs搜索的点不存在时,我们是在m x n这样的矩阵里面搜索的,所以当x或者y小于0或者超出矩阵的大小时,终止dfs
2.因为我们是要搜索与边界相连的’O’,因此当dfs搜索的当前点不是‘O’的时候,我们就可以直接结束dfs
void dfs(vector<vector<char>>& board, int x,int y) { if(x < 0 || x >= m || y < 0 || y >= n || board[x][y] != 'O') { return; } }
出口写好之后,我们需要来写对当前dfs搜索的点做的“动作”,这个“动作”就是指我们搜索到了与边界相连的并且值为’O‘的点,然后我们要对这个点进行改动
void dfs(vector<vector<char>>& board, int x,int y) { if(x < 0 || x >= m || y < 0 || y >= n || board[x][y] != 'O') { return; } board[x][y] = 'A'; }
基于上面的讨论我们是要把与边界值为’O’的点相连的值也为‘O’的点都用另一个字母进行填充,这里我选择的是’A’
对点进行改动之后,我们就要对这个点的上下左右再进行深一层的递归搜索
void dfs(vector<vector<char>>& board, int x,int y) { if(x < 0 || x >= m || y < 0 || y >= n || board[x][y] != 'O') { return; } board[x][y] = 'A'; dfs(board, x + 1, y);//下 dfs(board, x - 1, y);//上 dfs(board, x, y + 1);//右 dfs(board, x, y - 1);//左 }
写完递归之后我们就要来写主函数了,也就是dfs的入口我们需要做什么,上面讨论到我们需要从矩阵的边界开始dfs的搜索,也就是矩阵的四个边,写成代码如下
class Solution{ int m, n; void solve(vector<vector<char>>& board) { int m = int(board.size()); int n = int(board[0].size()); for(int i = 0; i < m; i++) { if(board[i][0] == 'O') { dfs(board, i, 0);//左边 } if(board[i][n - 1] == 'O') { dfs(board, i, n - 1);//右边 } } for(int j = 1; j < n - 1; j++) { if(board[0][j] == 'O') { dfs(board, 0, j);//上边 } if(board[m - 1][j] == 'O') { dfs(board, m - 1, j);//下边 } } } }
都加了一个if是因为可以直接判断边界是否为’O’如果不是直接跳过当前边界点
在做完上面的这些后,我们就需要一个最后的遍历来将值为‘A’的点恢复原样或者将值为’O‘的填充为’X‘,总共的代码如下:
完整代码:
class Solution{ int m, n; void dfs(vector<vector<char>>& board, int x,int y) { if(x < 0 || x >= m || y < 0 || y >= n || board[x][y] != 'O') { return; } board[x][y] = 'A'; dfs(board, x + 1, y);//下 dfs(board, x - 1, y);//上 dfs(board, x, y + 1);//右 dfs(board, x, y - 1);//左 } void solve(vector<vector<char>>& board) { int m = int(board.size()); int n = int(board[0].size()); for(int i = 0; i < m; i++) { if(board[i][0] == 'O') { dfs(board, i, 0);//左边 } if(board[i][n - 1] == 'O') { dfs(board, i, n - 1);//右边 } } for(int j = 1; j < n - 1; j++) { if(board[0][j] == 'O') { dfs(board, 0, j);//上边 } if(board[m - 1][j] == 'O') { dfs(board, m - 1, j);//下边 } } for(int i = 0; i < m; i++) { for(int j = 0; j < n; j++) { if(board[i][j] == 'A') { board[i][j] = 'O'; } else { board[i][j] = 'X'; } } } } }
大家好我是程序员云锦,我是一名计算机专业的大三学生,我的方向是前端以及算法,今后会在csdn上更新有关前端和算法的相关内容,希望大家多多捧场!三连评论我都会会一个个回访的!谢谢大家!!!