美文网首页
leetcode130 被围绕的区域

leetcode130 被围绕的区域

作者: 奥利奥蘸墨水 | 来源:发表于2020-04-10 00:04 被阅读0次

    题目

    被围绕的区域

    分析

    题目可以转换成:对每一个在边界上的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; //标记
                    }
                }                        
            }
        }
    };
    

    相关文章

      网友评论

          本文标题:leetcode130 被围绕的区域

          本文链接:https://www.haomeiwen.com/subject/nywkmhtx.html