【图论】Leetcode 130. 被围绕的区域【中等】

被围绕的区域

• 给你一个 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’。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
解题思路

• 1、界限上的 ‘O’ 及其连通的 ‘O’：这些 ‘O’ 是不会被 ‘X’ 围绕的。 必要找到所有这些 ‘O’，并将它们标记为特殊字符（例如 ‘#’)。
  
• 2、内部的 ‘O’：这些 ‘O’ 是被 ‘X’ 围绕的，必要填充为 ‘X’。
  
• 3、恢复特殊标记的 ‘O’：将特殊标记的字符（例如 ‘#’) 重新变回 ‘O’。
  

Java实现

1. public class SurroundedArea {
3.     public void solve(char[][] board) {
4.         if (board == null || board.length == 0) {
5.             return;
6.         }
8.         int m = board.length;
9.         int n = board[0].length;
11.         // Step 1: 标记边界 'O'为 '#'
12.         for (int i = 0; i < m; i++) {
13.             //第一列有0
14.             if (board[i][0] == 'O') {
15.                 dfs(board, i, 0);
16.             }
17.             //最后一列有0
18.             if (board[i][n - 1] == 'O') {
19.                 dfs(board, i, n - 1);
20.             }
21.         }
22.         for (int j = 0; j < n; j++) {
23.             //第一行有0
24.             if (board[0][j] == 'O') {
25.                 dfs(board, 0, j);
26.             }
27.             //最后一行有0
28.             if (board[m - 1][j] == 'O') {
29.                 dfs(board, m - 1, j);
30.             }
31.         }
33.         // Step 2: 用X替换 'O'
34.         for (int i = 0; i < m; i++) {
35.             for (int j = 0; j < n; j++) {
36.                 if (board[i][j] == 'O') {
37.                     board[i][j] = 'X';
38.                 }
39.             }
40.         }
42.         // Step 3: 把 '#' 还原成 'O'
43.         for (int i = 0; i < m; i++) {
44.             for (int j = 0; j < n; j++) {
45.                 if (board[i][j] == '#') {
46.                     board[i][j] = 'O';
47.                 }
48.             }
49.         }
50.     }
52.     /** dfs搜索 */
53.     private void dfs(char[][] board, int i, int j) {
54.         int m = board.length;
55.         int n = board[0].length;
56.         //边界条件判断
57.         if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != 'O') {
58.             return;
59.         }
60.         board[i][j] = '#';
61.         dfs(board, i - 1, j); // up
62.         dfs(board, i + 1, j); // down
63.         dfs(board, i, j - 1); // left
64.         dfs(board, i, j + 1); // right
65.     }
67.     public static void main(String[] args) {
68.         SurroundedArea surroundedArea = new SurroundedArea();
70.         // 示例输入
71.         char[][] board = {
72.             {'X', 'X', 'X', 'X'},
73.             {'X', 'O', 'O', 'X'},
74.             {'X', 'X', 'O', 'X'},
75.             {'X', 'O', 'X', 'X'}
76.         };
78.         // 处理矩阵
79.         surroundedArea.solve(board);
81.         // 打印处理后的矩阵
82.         for (char[] row : board) {
83.             for (char c : row) {
84.                 System.out.print(c + " ");
85.             }
86.             System.out.println();
87.         }
88.         // 输出应为：
89.         // X X X X
90.         // X X X X
91.         // X X X X
92.         // X O X X
93.     }
94. }

复制代码

时间空间复杂度

• 时间复杂度：O(m * n)，此中 m 和 n 分别是矩阵的行数和列数。每个元素最多访问一次。
  
• 空间复杂度：O(m * n)，在最坏情况下递归栈的深度可能达到矩阵元素总数。
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。