leetcode 130. 被围绕的区域

佚名 6年前 (2019-04-24) 随笔 361人围观抢沙发百度已收录

首先这当然考的是图的遍历。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

其次，这道题是不考虑与边界相连的O的，因此可以在条件判断时加一个是否与边界相连。由于图比较大的情况下，每一个都重新判断会使得重复遍历，因此建立一个visit二维数组，将所有与边界相连通的O全部遍历标记出来，然后再从边界内部的图形开始遍历。

第二，由于大图递归dfs会产生错误，递归深度过深，因此使用队列进行bfs遍历，避免溢出；

第三，对于坐标的存储使用pair较为方便，pair使用方法为，pair<type1,type2> p;进行定义，例如 pair<int,int>。使用p.first,p.second进行访问，（first和second不是方法是属性）。同时使用make_pair(i,j)这个函数来进行初始化或赋值；

代码如下：

class Solution {
public:
    vector<vector<int> > dirs={{-1,0},{0,-1},{0,1},{1,0}};
    void solve(vector<vector<char>>& board) {
        int m=board.size();
        if(m<=2) return;
        int n=board[0].size();
        if(n<=2) return;
        vector<vector<char> > visit=board;
        for(int i=0;i<m;i++){
            if(visit[i][0]=='O')
                dfs(visit,i,0);
            if(visit[i][n-1]=='O')
                dfs(visit,i,n-1);
        }
        for(int j=0;j<n;j++){
            if(visit[0][j]=='O')
                dfs(visit,0,j);
            if(visit[m-1][j]=='O')
                dfs(visit,m-1,j);
        }
        
        for(int i=1;i<m-1;i++){
            for(int j=1;j<n-1;j++){
                if(visit[i][j]=='O')
                    bfs(board,i,j);
            }
        }
    }
    void dfs(vector<vector<char> >& board,int i,int j){
        int m=board.size();int n=board[0].size();
        if(i<0 || i>m-1 || j<0 || j>n-1 || board[i][j]!='O') return;
        board[i][j]='X';
        for(auto dir:dirs){
            dfs(board,i+dir[0],j+dir[1]);
        }
    }
    void bfs(vector<vector<char> >& board,int i,int j){
        int m=board.size();int n=board[0].size();
        board[i][j]='X';
        queue< pair<int,int> > q;
        pair<int,int> tmp=make_pair(i,j);
        q.push(tmp);
        while(!q.empty()){
            pair<int,int> cur=q.front();
            q.pop();
            board[cur.first][cur.second]='X';
            for(auto dir:dirs){
                int a=cur.first+dir[0],b=cur.second+dir[0];
                if(a<=0 || a>=m-1 || b<=0 || b>=n-1 || board[i][j]!='O') continue;
                tmp=make_pair(a,b);
                q.push(tmp);
            }
        }
    }
};