刷题第5篇：被包围的区域
- 2020 年 2 月 25 日
- 筆記
各位同学好！本周的刷题结果又来了！本周刷的一些题目里面，觉得下面这道题目比较有点意思吧！有时候我们容易陷入一个思想的误区里面，稍微使用一下逆向思维，可能会带来不一样的感受！
下面这道题目，属于LeetCode上面的第130题。
题目描述
题目的链接：
https://leetcode-cn.com/problems/surrounded-regions/
这道题看上去有点像类似于行军作战，一旦字母"O"被字母"X"包围，那么字母"X"就会"干掉"字母"o"。类似于下面这样
XXXXXXXXXX XXXXXXXXXX OOOXXXXXOO OOOXXXXXOO XXXXXOOXXX -----> XXXXXXXXXX XXOOXXXXXX XXXXXXXXXX XXXXXOOOOO XXXXXOOOOO
解法一：逐个进行DFS
解法一属于一种直观的思考。主要就是在用一种直观的思路，使用深度优先算法DFS，逐行逐列遍历每一个元素。
当元素为字母"O"的时候，对其周围的元素进行探索，查看是否能够遇到一个边界元素"O"。
如果进行DFS的过程中，没有遇到边界的字母"O"，则将此过程中所有的字母"O"更换为字母"X"。
如果进行DFS过程中，遇到了一个边界字母"O"，则对此过程中遍历的字母都不进行操作。
实现代码如下：
public void solve(char[][] board) { int rows = board.length; if (rows == 0) { return; } int cols = board[0].length; //考虑除去边界以外的所有 O for (int i = 1; i < rows - 1; i++) { for (int j = 1; j < cols - 1; j++) { if (board[i][j] == 'O') { //visited 用于记录 DFS 过程中已经访问过的节点 HashSet<String> visited = new HashSet<>(); //如果没有到达边界，就把当前 O 置为 X if (!solveHelper(i, j, board, visited)) { board[i][j] = 'X'; } } } } } private boolean solveHelper(int row, int col, char[][] board, HashSet<String> visited) { //是否访问过 if (visited.contains(row + "@" + col)) { return false; } visited.add(row + "@" + col); //到达了 X 直接返回 false if (board[row][col] == 'X') { return false; } if (row == 0 || row == board.length - 1 || col == 0 || col == board[0].length - 1) { return true; } //分别尝试四个方向 if (solveHelper(row - 1, col, board, visited, memoization) || solveHelper(row, col - 1, board, visited, memoization) || solveHelper(row + 1, col, board, visited, memoization) || solveHelper(row, col + 1, board, visited, memoization)) { return true; } else { return false; } }
但是遗憾的是，这样的代码提交到LeetCode上面之后，运行时间超时了，无法通过。
解法二：由外向内
在上面的解法一中，我们对整个board进行遍历。在每次的遍历过程中，我们需要对所遇到的字母"O"先进行保存处理，因为我们不知道此字母在后面的遍历过程中是否会遇到的边界上的"O"，所以在内存上面也会遇到很多问题。
那么我们尝试着换一种思路。经过分析可以发现：在所有的字母"O"中，可以将其分为两类，一类是被包围的"O"，最后需要被字母"X"替换；还有一类是没有被包围的"O"，最后不需要进行任何操作。
如果我们的起始字母"O"，就已经处于边界点，那么根据边界点"O"进行DFS搜索得到的字母"O"都属于没有被包围的点。
记录下这些没有被包围的点之后，那么可以将剩下的"O"进行替换处理。
所以，我们解法二的处理应该将边界点"O"作为入口，遍历每个邻居节点。
与此同时，我们可以对未被包围的字母"O"，使用一个"#"作为占位符处理。全部遍历完之后，先将剩余的"O"替换为"X"，再将"#"替换为"O"。
实现代码如下：
public void solve(char[][] board) { if (board.length < 3 || board[0].length < 3){ return; } int[][] direction = {{-1,0},{1,0},{0,1},{0,-1}}; int m = board.length; int n = board[0].length; for (int i = 0; i < m ; i++){ for (int j =0 ; j < n ; j++){ if (board[i][j] == 'O' && T130_isEdge(i,j,board)){//从边界开始向内进行腐蚀 T130(i,j,direction,board); } } } for (int i = 0; i < m ; i++){ for (int j =0 ; j < n ; j++){ if (board[i][j] == 'O'){//从边界开始向内进行腐蚀 board[i][j] = 'X'; }else if (board[i][j] == '#'){//将未被包含的字符'O'还原回来 board[i][j] = 'O'; } } } } public void T130 (int row,int column,int[][] direction,char[][] board ){ if (board[row][column] == '#' || board[row][column] == 'X'){ return; } board[row][column] = '#';//使用一个占位符表示未被包围的字符'O' for (int i = 0 ; i < direction.length ; i++){ //获取新的坐标 int X = row+direction[i][0]; int Y = column+direction[i][1]; if (T130_helper(X,Y,board.length,board[0].length)){//如果新坐标在内部 T130(X,Y,direction,board); } } } public boolean T130_isEdge(int row,int column,char[][] board){ return row == 0 || column == 0 || row == board.length-1 || column == board[0].length-1; } public boolean T130_helper (int X,int Y,int row,int column){ return X >= 0 && X <= row-1 && Y >= 0 && Y <= column-1 ; }
上面的代码运行通过了！
总结
在解法一中，我们在使用DFS的时候，由于每次遍历开始，我们无法区分当前"O"属于哪一类，所以需要等待，一直到最后的字母"O"，结束之后，才可以进行判断。
在解法二中，我们使用的是一种逆向思维，从边界开始思考，那么在使用DFS进行遍历的时候，可以直接将其归为未被包围的"O"点，大大减少了我们判断的难度。所以时间会更加快一点！
