被围绕的区域【深度(广度)优先搜索】

给定一个二维的矩阵，包含 'X' 和 'O'（字母 O）。 找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。

示例:

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
解释:

被围绕的区间不会存在于边界上，换句话说，任何边界上的 ‘O’ 都不会被填充为 ‘X’。 任何不在边界上，或不与边界上的 ‘O’ 相连的 ‘O’ 最终都会被填充为 ‘X’。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

分析：<br />    任何边界上的O都不会被填充为X; 所以: 所有不被包围的O都直接或间接与边界上O相连；<br />    1、先判断O是否与边界上的O相连，以边界上的O为起点，采用深度优先搜索的方式对直接或间接<br />    与边界上的O相连O标记为M;<br />    2、对于没有被标记的M, 则其被X包围，应该用X填充；

一、深度优先搜索(递归)

int m;
int n;
void dfs_mark(vector<vector<char>> &board, int row, int col)
{
    if(row<0 || col<0 || row>=m || col>=n || board[row][col]!='O')
        return;
    board[row][col]='M';
    dfs_mark(board, row-1, col); // up
    dfs_mark(board, row+1, col); // down
    dfs_mark(board, row, col-1); // left
    dfs_mark(board, row, col+1); // right
}

void solve(vector<vector<char>>& board) 
{
    m = board.size();
    if (m<=2)
        return;
    n = board[0].size();

    // vertical board
    for(int i=0; i<m; ++i)
    {
        dfs_mark(board, i, 0);
        dfs_mark(board, i, n-1);
    }

    // horizontal board
    for(int j=1; j<n-1; ++j)
    {
        dfs_mark(board, 0, j);
        dfs_mark(board, m-1, j);
    }

    // fill 'O' with 'X'
    for(int i=0; i<m; ++i)
    {
        for(int j=0; j<n; ++j)
        {
            if (board[i][j] == 'O')
                board[i][j] = 'X';
            else if(board[i][j] == 'M')
                board[i][j] = 'O';
        }
    }
}
// 时间复杂度：O(m*n)
// 空间复杂度：O(m*n)

二、广度优先搜索（用到队列queue>）

const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
void bfs_mark(vector<vector<char>> &board, int m, int n)
{
    queue<pair<int, int>> Q;
    // vertical border
    for(int i=0; i<m; ++i)
    {
        if (board[i][0] == 'O')
            Q.emplace(i, 0);
        if (board[i][n-1] == 'O')
            Q.emplace(i, n-1);
    }

    // horizontal border
    for(int j=1; j<n-1; ++j)
    {
        if(board[0][j] == 'O')
            Q.emplace(0, j);
        if (board[m-1][j] == 'O')
            Q.emplace(m-1, j);
    }

    while(!Q.empty()){
        int x = Q.front().first;
        int y = Q.front().second;
        Q.pop();
        board[x][y] = 'M';

        // up, down, left, right
        for(int k=0; k<4; ++k)
        {
            int x_dx = x + dx[k];
            int y_dy = y + dy[k];
            if (x_dx<0 || x_dx>=m || y_dy<0 || y_dy>=n || board[x_dx][y_dy]!='O')
                continue;
            Q.emplace(x_dx, y_dy);
        }
    }
}
void solve(vector<vector<char>>& board)
{
    int m = board.size();
    if (m<=2)
        return;
    int n = board[0].size();
    bfs_mark(board, m, n);

    // fill O with X
    for(int i=0; i<m; ++i)
    {
        for(int j=0; j<n; ++j)
        {
            if (board[i][j] == 'M')
                board[i][j] = 'O';
            else if (board[i][j] == 'O')
                board[i][j] = 'X';
        }
    }
}

欢迎交流，不吝赐教！