[一道中等难度题] 被围绕的区域

给一个二维的矩阵,包含 \’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;
    }
}

更多题解参见

Click to rate this post!
[Total: 0 Average: 0]

相关文章

发表回复

您的电子邮箱地址不会被公开。