130. 被围绕的区域

一时失言乱红尘 2022-12-12 15:29 128阅读 0赞

# 题目： #

[130. 被围绕的区域][130.]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center]

# 题解：DFS + 沉岛思想 #

## 1. 解释一： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 3]

## 2. 解释二： ##

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

## 3. 解释三： ##

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

# 代码：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();
            }
        }
    }

# 参考： #

1.  [被围绕的区域，DFS+BFS，思路明确，注释详细][DFS_BFS]
2.  [被围绕的区域][Link 1]
3.  [bfs+递归dfs+非递归dfs+并查集][bfs_dfs_dfs]
4.  [DFS + BFS + 并查集][DFS _ BFS _]
5.  [DFS、并查集（Java）][DFS_Java]
6.  [c++,beats 94.65%,easy to understand][c_beats 94.65_easy to understand]

[130.]: https://leetcode-cn.com/problems/surrounded-regions/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/a451cc9b220c4d388615f59cfbe2e528.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/3200c333d6254a12a00773b889c2192a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/2017592f15c64f6daf7edcd03f408d7f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/9bc0e2f96ded4dcf9220640b80ae2166.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221123/ad68ded1668249b5bcb4cb5fd01b0a72.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221123/0c102915ff4f423aaaa4ea002794fb84.png
[DFS_BFS]: https://leetcode-cn.com/problems/surrounded-regions/solution/dfsbfssi-lu-ming-que-zhu-shi-xiang-xi-by-zui-weng-/
[Link 1]: https://leetcode-cn.com/problems/surrounded-regions/solution/bei-wei-rao-de-qu-yu-by-leetcode-solution/
[bfs_dfs_dfs]: https://leetcode-cn.com/problems/surrounded-regions/solution/bfsdi-gui-dfsfei-di-gui-dfsbing-cha-ji-by-ac_pipe/
[DFS _ BFS _]: https://leetcode-cn.com/problems/surrounded-regions/solution/dfs-bfs-bing-cha-ji-by-powcai/
[DFS_Java]: https://leetcode-cn.com/problems/surrounded-regions/solution/dfs-bing-cha-ji-java-by-liweiwei1419/
[c_beats 94.65_easy to understand]: https://leetcode-cn.com/problems/surrounded-regions/solution/cbeats-9465easy-to-understand-by-zzyuting/