leetcode130 被围绕的区域

题目

被围绕的区域

分析

题目可以转换成：对每一个在边界上的O开始遍历，标定一篇区域。之后再遍历整个矩阵，没被标定且是O的位置，都应该被填成X。标定区域用bfs和dfs都可以，我这里使用了bfs。

代码

class Solution {
public:
    vector<vector<int>> bo;
    void solve(vector<vector<char>>& board) {
        if (board.empty()){
            return;
        }
        
        int row = board.size();
        int col = board[0].size();

        for (int i = 0; i < row; i++){
            vector<int> vec;
            for (int j = 0; j < col; j++){
                vec.push_back(0);
            }
            bo.push_back(vec);
        }

        //上边
        for (int i = 0; i < col; i++){
            if (bo[0][i] == 0 && board[0][i] == 'O'){
                bfs(board, 0, i);
            }
        }

        //左边
        for (int i = 0; i < row; i++){
            if (bo[i][0] == 0 && board[i][0] == 'O'){
                bfs(board, i, 0);
            }
        }

        //下边
        for (int i = 0; i < col; i++){
            if (bo[row - 1][i] == 0 && board[row - 1][i] == 'O'){
                bfs(board, row - 1, i);
            }
        }

        //右边
        for (int i = 0; i < row; i++){
            if (bo[i][col - 1] == 0 && board[i][col - 1] == 'O'){
                bfs(board, i, col - 1);
            }
        }

        for (int i = 0; i < row; i++){
            for (int j = 0; j < col; j++){
                if (board[i][j] == 'O' && bo[i][j] == 0){
                    board[i][j] = 'X';
                }
            }
        }

    }

    void bfs(vector<vector<char>>& board, int i ,int j){

        int next[4][2] = {{0, 1},{0, -1},{1, 0},{-1, 0}};
        int row = board.size();
        int col = board[0].size();

        queue<pair<int,int>> que;
        que.push(make_pair(i, j)); //首节点入队
        bo[i][j] = 1; //标记首节点

        while (!que.empty()){
            int cur_i = que.front().first;
            int cur_j = que.front().second;

            // cout << "当前位置: " << cur_i << " " << cur_j << endl;
            
            que.pop();
            
            for (int m = 0; m < 4; m++){
                int next_i = cur_i + next[m][0];
                int next_j = cur_j + next[m][1];
                // cout << "下一步位置: " << next_i << " " << next_j << endl;

                //横坐标合法性检查
                if (next_i >= row || next_i < 0){
                    // cout << "横坐标不合法" << endl;
                    continue;
                }
                //纵坐标合法性检查
                if (next_j >= col || next_j < 0){
                    // cout  << "纵坐标不合法" << endl;
                    continue;
                }

                //是陆地且且没到过
                if (board[next_i][next_j] == 'O' && bo[next_i][next_j] == 0){
                    // cout << "都合法" << endl;
                    que.push(make_pair(next_i, next_j));
                    // cnt++;    //计数
                    bo[next_i][next_j] = 1; //标记
                }
            }                        
        }
    }
};