Leetcode 被围绕的区域

算法思想（解题思路）：

这道题的核心是 将所有被边界包围的 'O' 保留下来，而将其他被围绕的 'O' 转换为 'X'。为了实现这一目标，我们可以分三步完成：

---

第一步：标记边界及其相连的 'O' 为特殊标记（例如 'E'）

1. 目标：

   • 找到所有与矩阵边界相连的 'O'，将它们和与它们直接相连的所有 'O' 标记为一个特殊字符（比如 'E'）。
   • 这些 'O' 是不能被包围的，因为它们直接或间接与边界相连。

2. 方法：

   • 使用深度优先搜索（DFS）或广度优先搜索（BFS）从矩阵边界上的 'O' 开始，向四个方向扩散，将与边界相连的 'O' 都标记为 'E'。
   • 这样，剩下的 'O' 就是被完全包围的。

---

第二步：遍历整个矩阵，处理不同状态的字符

1. 目标：

   • 将矩阵中所有剩下的 'O' 转换为 'X'，因为这些 'O' 是被完全包围的区域。
   • 将之前标记为 'E' 的字符还原为 'O'，因为它们是不被包围的。

2. 方法：

   • 遍历矩阵中的每一个元素，根据字符值进行判断：
     • 如果是 'O'，说明是被完全包围的区域，改为 'X'。
     • 如果是 'E'，说明是边界或与边界相连的 'O'，改回 'O'。

---

第三步：输出最终结果

经过上述处理，矩阵会满足题目要求，所有被包围的 'O' 转换为 'X'，而没有被包围的 'O' 保留下来。

---

算法流程详解：

1. 初始化矩阵大小：

   • 首先判断输入矩阵是否为空。如果为空，直接返回。

2. 标记边界：

   • 遍历矩阵的 四个边界（第一行、最后一行、第一列、最后一列）。
   • 对边界上的每个 'O'，用DFS递归标记其相连的 'O' 为 'E'。

3. 遍历矩阵并修改字符：

   • 遍历矩阵中的所有元素：
     • 如果当前字符是 'O'，说明它是被包围的，转换为 'X'。
     • 如果当前字符是 'E'，说明它是与边界相连的，还原为 'O'。

---

时间与空间复杂度分析：

1. 时间复杂度：O(m * n)

   • 遍历矩阵的每个单元格一次，并且在标记边界时每个单元格也最多访问一次。

2. 空间复杂度：

   • 递归栈空间：使用DFS时，递归深度与矩阵的大小相关，最坏情况下需要 O(m * n) 的栈空间。

---

示例说明：

输入：

board = [['X', 'X', 'X', 'X'],['X', 'O', 'O', 'X'],['X', 'X', 'O', 'X'],['X', 'O', 'X', 'X']
]

执行过程：

1. 标记边界：

   • 第一步遍历边界：发现 (3,1) 是 'O'，并通过DFS标记与其相连的所有 'O' 为 'E'。
   • 标记后的矩阵：

     [['X', 'X', 'X', 'X'],['X', 'O', 'O', 'X'],['X', 'X', 'O', 'X'],['X', 'E', 'X', 'X']
     ]
     

2. 遍历矩阵修改字符：

   • 将所有未标记的 'O' 转换为 'X'。
   • 将标记为 'E' 的字符还原为 'O'。
   • 最终矩阵：

     [['X', 'X', 'X', 'X'],['X', 'X', 'X', 'X'],['X', 'X', 'X', 'X'],['X', 'O', 'X', 'X']
     ]
     

输出：

[['X', 'X', 'X', 'X'],['X', 'X', 'X', 'X'],['X', 'X', 'X', 'X'],['X', 'O', 'X', 'X']
]

总结：

通过将与边界相连的 'O' 特殊标记，我们可以有效区分哪些 'O' 是被围绕的，最终实现题目要求。

class Solution {public void solve(char[][] board) {if(board == null || board.length == 0)  return;//获取矩阵的行和列int rows = board.length;int cols = board[0].length;for(int i = 0; i < rows; i++) {if(board[i][0] == 'O') {dfs(board, i, 0);}if(board[i][cols - 1] == 'O') {dfs(board, i, cols - 1);}}for(int j = 0; j < cols; j++) {if(board[0][j] == 'O') {dfs(board, 0, j);}if(board[rows - 1][j] == 'O') {dfs(board, rows - 1, j);}}//然后将剩下的O转换为X, E 转换回 Ofor(int i = 0; i < rows; i++) {for(int j = 0; j < cols; j++) {if(board[i][j] == 'O') {board[i][j] = 'X';}if(board[i][j] == 'E') {board[i][j] = 'O';}}}}private void dfs(char[][] board, int row, int col) {//首先检查是否越界if(row < 0 || row >= board.length || col < 0 || col >= board[0].length || board[row][col] != 'O') {return;}//将O标记为Eboard[row][col] = 'E';dfs(board, row + 1, col);dfs(board, row - 1, col);dfs(board, row, col + 1);dfs(board, row, col - 1);}
}