题目：

130. 被围绕的区域

题解：DFS + 沉岛思想

1. 解释一：

2. 解释二：

3. 解释三：

代码：DFS + 沉岛思想

public class code130 { // 思路: DFS + 沉岛思想 // 步骤1：对于每一个边界上的 O，我们以它为起点，标记所有与它直接或间接相连的字母'O'为'M' // 步骤2：最后我们遍历这个矩阵，替换'M'为'O'，'O'为'X' int m = 0; // 行数 int n = 0; // 列数 public void solve(char[][] board) { // 设矩阵为 m 行 n 列 // java二维矩阵的行数和列数可能不同，并且每一行的列数可能都不一样 // 但是肯定是先后行再有列，而且根据题目要求，在这里每一行的列数都是相同的 m = board.length; // 行数m if(m == 0) // 行数为0，board为空 { return; } n = board[0].length;// 列数 // 搜索上下边界的'O' for(int i = 0; i < n; i++) { if(board[0][i] == 'O') // 第一行 { dfs(board, 0 , i); // 标记 } if(board[m - 1][i] == 'O') // 最后一行 { dfs(board, m - 1, i); // 标记 } } // 搜索左右边界的'O' for(int i = 1; i < m - 1; i++) // 此时第一行和最后一行已经在搜索上下边界的'O'时，搜过了。 { if(board[i][0] == 'O') // 第一列 { dfs(board, i, 0); // 标记 } if(board[i][n - 1] == 'O') // 最后一列 { dfs(board, i, n - 1); // 标记 } } // 标记完，再次遍历，现在矩阵中可能有3中字符，'X','M','O' for(int i = 0; i < m; i++) { for(int j = 0; j < n; j++) { if(board[i][j] == 'X') // 遇到'X'，直接跳过 { continue; } else if(board[i][j] == 'O') // 出现没被标记过的'O'，应该被填充为'X' { board[i][j] = 'X'; } else if(board[i][j] == 'M') // 出现被标记过的'O'，不应该被填充为'X'，需要恢复为'O' { board[i][j] = 'O'; } } } } public void dfs(char[][] board, int x, int y) { // 越界或者不是字符'O'终止 if(x < 0 || x >= m || y < 0 || y >= n || board[x][y] != 'O') { return; } board[x][y] = 'M'; // 修改为'M'表示这个字符被标记了 // 搜索四个方向 dfs(board, x - 1, y); // 上 dfs(board, x + 1, y); // 下 dfs(board, x, y - 1); // 左 dfs(board, x, y + 1); // 右 } public static void main(String[] args) { char board[][] = {{'X', 'X', 'X', 'X'}, {'X', 'O', 'O', 'X'}, {'X', 'X', 'O', 'X'}, {'X', 'O', 'X', 'X'}}; for(int i = 0; i < board.length; i++) { for(int j = 0; j < board[0].length; j++) { System.out.print(board[i][j] + " "); } System.out.println(); } System.out.println("***************************************"); code130 test = new code130(); test.solve(board); for(int i = 0; i < board.length; i++) { for(int j = 0; j < board[0].length; j++) { System.out.print(board[i][j] + " "); } System.out.println(); } } }

参考：

被围绕的区域，DFS+BFS，思路明确，注释详细被围绕的区域bfs+递归dfs+非递归dfs+并查集DFS + BFS + 并查集DFS、并查集（Java）c++,beats 94.65%,easy to understand