Leetcode.130.Surrounded Regions

题目

给定一个二维数组, 数组元素包含'X'和'O'. 如果'O'被'X'围起来, 就将'O'改成'X'.

Input:   {{'X', 'X', 'X', 'X'},
          {'X', 'O', 'O', 'X'},
          {'X', 'X', 'O', 'X'},
          {'X', 'O', 'X', 'X'}}

Output:  {{'X', 'X', 'X', 'X'},
          {'X', 'X', 'X', 'X'},
          {'X', 'X', 'X', 'X'},
          {'X', 'O', 'X', 'X'}} 

思路

农村包围城市, 当最外围出现'O'时, 才能和内部连通留下'O'. 遍历最外圈的元素, 对最外围元素进行上下左右方向递归.
通过修改'O', 来标记需要修改的元素.
时间复杂度O(n²)
空间复杂度O(1)

void solveRecrution(vector<vector<char>>& board, int i, int j) {
    // 保存需要置为'O'的元素
    board[i][j] = '?';
    if (i > 0 && board[i-1][j] == 'O') {
        solveRecrution(board, i-1, j);
    }
    if (i + 1 < board.size() && board[i+1][j] == 'O') {
        solveRecrution(board, i+1, j);
    }
    if (j > 0 && board[i][j-1] == 'O') {
        solveRecrution(board, i, j-1);
    }
    if (j + 1 <board[i].size() && board[i][j+1] == 'O') {
        solveRecrution(board, i, j+1);
    }
}

// 递归
void solve(vector<vector<char>>& board) {
    if (board.size() < 2) return ;
    int row = (int)board.size();
    int col = (int)board[0].size();
    // 遍历上下边
    for (int j = 0; j < col; ++j) {
        if (board[0][j] == 'O') {
            solveRecrution(board,0,j);
        }
        if (board[row-1][j] == 'O') {
            solveRecrution(board, row-1, j);
        }
    }
    // 遍历左右边
    for (int i = 1; i < row-1; ++i) {
        if (board[i][0] == 'O') {
            solveRecrution(board,i,0);
        }
        if (board[i][col-1] == 'O') {
            solveRecrution(board,i,col-1);
        }
    }

    for (int i = 0; i < board.size(); ++i) {
        for (int j = 0; j < col; ++j) {
            if (board[i][j] == 'O') {
                board[i][j] = 'X';
            } else if (board[i][j] == 'A') {
                board[i][j] = 'O';
            }
        }
    }
}

总结

DFS, 关键是分析具体问题, 找到递归的突破点. 安装常规从左到右, 从上到下就很难分析, 容易