给一个二维的矩阵，包含 ‘X’ 和 ‘O’, 找到所有被 ‘X’ 围绕的区域，并用 ‘X’ 替换其中所有的 ‘O’。

点此在线做题

样例 1:

输入:   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 

样例 2:

输入:    X X X X   X O O X   X O O X   X O X X 输出:    X X X X   X O O X   X O O X   X O X X 

[题解]

算法：DFS 思路：先从外围开始，只有身处外围的 O 是无法被包围的，同理，与一个无法被包围的 O 相连的 O 也是无法被包围的。

• 从外围开始，若遇到边界的 O，则将其标记为 ，意味无法被包围的 O 依次对外圈的“O”的四个方向做 DFS，将其可以到达 O 临时设置为
• 最后，遍历数组， 将无法被包围的 O，也就是此时被标记为 * 改为 O ； X 不变； 将可以被包围的区域，即没被标记过的 O 变为 X

复杂度分析

• 时间复杂度 O(n*m) 搜索一次图即可
• 空间复杂度 O(n*m) 图的大小

public class Solution {     /**      * @param board a 2D board containing 'X' and 'O'      * @return void      */     public void surroundedRegions(char[][] board) {         if (board == null || board.length == 0 || board[0].length == 0) {             return ;         }         int n = board.length,m = board[0].length;         //四周向中间搜         for (int i = 0; i < n;i++) {             for (int j = 0;j < m;j++) {                 if (!is_border(i,j,n,m)) {                     continue;                 }                 if (board[i][j] == 'O') {                     dfs(board , i , j);                 }             }         }                  //遍历图，更新结果         for (int i = 0;i < n;i++) {             for (int j = 0;j < m;j++) {                 if (board[i][j] == 'O') {                     board[i][j] = 'X';                 }                 else if (board[i][j] == '*') {                     board[i][j] = 'O';                  }             }         }     }          public void dfs(char[][] board , int x , int y){         //保证当前点在图中         if (x < 0 || y < 0 || x >= board.length || y >= board[0].length) {             return ;         }         if (board[x][y] != 'O') {             return ;         }         board[x][y] = '*';         dfs(board , x + 1, y);         dfs(board , x - 1, y);         dfs(board , x , y + 1);         dfs(board , x , y - 1);     }     public boolean is_border(int x,int y,int n,int m) {//判断是否边界         if (x == 0 || y == 0 || x == n - 1||y == m - 1) {             return true;         }         return false;     } } 

更多题解参见

大佬有話說 (0)