[Leetcode][第130题][JAVA][被围绕的区域][DFS][BFS]

迈不过友情╰ 2022-11-26 09:51 109阅读 0赞

#### 【问题描述】\[中等\] ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]

#### 【解答思路】 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]

###### 1. 深度优先搜索 ######

使用深度优先搜索实现标记操作。在下面的代码中，我们把标记过的字母 O 修改为字母 A。  
**复杂度**  
![在这里插入图片描述][20200811205848502.png]

class Solution { 
        int[] dx = { 1, -1, 0, 0};
        int[] dy = { 0, 0, 1, -1};
    
        public void solve(char[][] board) { 
            int n = board.length;
            if (n == 0) { 
                return;
            }
            int m = board[0].length;
            Queue<int[]> queue = new LinkedList<int[]>();
            for (int i = 0; i < n; i++) { 
                if (board[i][0] == 'O') { 
                    queue.offer(new int[]{ i, 0});
                }
                if (board[i][m - 1] == 'O') { 
                    queue.offer(new int[]{ i, m - 1});
                }
            }
            for (int i = 1; i < m - 1; i++) { 
                if (board[0][i] == 'O') { 
                    queue.offer(new int[]{ 0, i});
                }
                if (board[n - 1][i] == 'O') { 
                    queue.offer(new int[]{ n - 1, i});
                }
            }
            while (!queue.isEmpty()) { 
                int[] cell = queue.poll();
                int x = cell[0], y = cell[1];
                board[x][y] = 'A';
                for (int i = 0; i < 4; i++) { 
                    int mx = x + dx[i], my = y + dy[i];
                    if (mx < 0 || my < 0 || mx >= n || my >= m || board[mx][my] != 'O') { 
                        continue;
                    }
                    queue.offer(new int[]{ mx, my});
                }
            }
            for (int i = 0; i < n; i++) { 
                for (int j = 0; j < m; j++) { 
                    if (board[i][j] == 'A') { 
                        board[i][j] = 'O';
                    } else if (board[i][j] == 'O') { 
                        board[i][j] = 'X';
                    }
                }
            }
        }
    }

###### 2. 广度优先搜索 ######

以使用广度优先搜索实现标记操作。在下面的代码中，我们把标记过的字母 O 修改为字母 A  
**时间复杂度：O(N) 空间复杂度：O(1)**

#### 【总结】 ####

###### 1. 细节： ######

1.1 方向定义  
int\[\] dx = \{1, -1, 0, 0\};  
int\[\] dy = \{0, 0, 1, -1\};  
1.2 边界判断  
if (mx < 0 || my < 0 || mx >= n || my >= m || board\[mx\]\[my\] != ‘O’) \{  
continue;  
\}

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

###### 2.DFS BFS 思路不复杂 注意细节 多写几遍 ######

转载链接：https://leetcode-cn.com/problems/surrounded-regions/solution/bei-wei-rao-de-qu-yu-by-leetcode-solution/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]: /images/20221124/978b46aac49049b58548c2f15f760463.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]: /images/20221124/7eb50e3385e844628e12ba5acf287833.png
[20200811205848502.png]: /images/20221124/2365f8e489a548fea8f2c367467a1f46.png