首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【leetcode】Surrounded Regions

【leetcode】Surrounded Regions

作者头像
阳光岛主
发布2019-02-19 11:38:24
4300
发布2019-02-19 11:38:24
举报
文章被收录于专栏:米扑专栏米扑专栏

Question :

Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region .

For example,

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

Anwser 1 :       DFS

class Solution {
public:
    void DFS(vector<vector<char> > &board, int i, int j){
        if(i >= board.size() || j >= board[0].size()) return;
        
        if(board[i][j] == 'O'){
            board[i][j] = '#';
        
            DFS(board, i-1, j);  // to left
            DFS(board, i+1, j);  // to right
            DFS(board, i, j-1);  // to up
            DFS(board, i, j+1);  // to down
        }
    }

    void solve(vector<vector<char>> &board) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        if(board.empty()) return;
        
        int len = board[0].size();  // one row length
        
        for(int i = 1; i < len - 1; i++){
            DFS(board, i, 0);        // left
            DFS(board, i, len-1);    // right
        }
        
        for(int j = 0; j < len; j++){
            DFS(board, 0, j);        // up
            DFS(board, len-1, j);    // down
        }
        
        //change 'O' to 'X'
        for(int i = 0; i < len; i++){
            for(int j = 0; j < len; j++){
                if(board[i][j] == 'O') board[i][j] = 'X';
                if(board[i][j] == '#') board[i][j] = 'O';
            }
        }
    }
};

Anwser 2 :  BFS

class Solution {
public:
    void enQ(vector<vector<char>> &board, int row, int col, int len, queue<int> &qu){
        if(row < 0 || row >= len || col < 0 || col >= len) return;
        if(board[row][col] == 'O'){
            board[row][col] = '#';
            qu.push(row * len + col);
        }
    }

    void BFS(vector<vector<char> > &board, int row, int col, int len, queue<int> &qu){
        enQ(board, row, col, len, qu);
        
        while(!qu.empty()){
            int val = qu.front();
            qu.pop();
            
            int row = val / len;
            int col = val % len;
        
            BFS(board, row-1, col, len, qu);  // to left
            BFS(board, row+1, col, len, qu);  // to right
            BFS(board, row, col-1, len, qu);  // to up
            BFS(board, row, col+1, len, qu);  // to down
        }
    }

    void solve(vector<vector<char>> &board) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        if(board.empty()) return;
        
        int len = board[0].size();  // one row length
        queue<int> Q;
        
        for(int i = 1; i < len - 1; i++){
            BFS(board, i, 0, len, Q);        // left
            BFS(board, i, len-1, len, Q);    // right
        }
        
        for(int j = 0; j < len; j++){
            BFS(board, 0, j, len, Q);        // up
            BFS(board, len-1, j, len, Q);    // down
        }
        
        //change 'O' to 'X'
        for(int i = 0; i < len; i++){
            for(int j = 0; j < len; j++){
                if(board[i][j] == 'O') board[i][j] = 'X';
                if(board[i][j] == '#') board[i][j] = 'O';
            }
        }
    }
};

Anwser 3 :   BFS  in Java

public class Solution {
    int m,n;
    char[][] board;
    Queue<Integer> queue=new LinkedList<Integer>();
    
    void fill(int x, int y){
        if(x<0 || x>=m || y<0 || y>=n || board[x][y]!='O') return;
        queue.offer(x*m+y);
        board[x][y]='D';
    }
    
    void bfs(int x, int y){
        fill(x,y);
        
        while(!queue.isEmpty()){
            int curr=queue.poll();
            int i=curr/n;
            int j=curr%n;
            
            fill(i-1,j);
            fill(i+1,j);
            fill(i,j-1);
            fill(i,j+1);
        }
    }
    
    public void solve(char[][] board){
        if(board==null || board.length==0) return;
        this.board=board;
        m=board.length;
        n=board[0].length;
        
        for(int j=0;j<n;j++){
            bfs(0,j);
            bfs(m-1,j);
        }
        
        for(int i=1;i<m-1;i++){
            bfs(i,0);
            bfs(i,n-1);
        }
        
        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]=='D') board[i][j]='O';
            }
    }
}

注意点:

1) 方法1通过,方法2不通过,方法3有时通过有时不通过(不通过与方法2编译错误一致)

2) 查了int在c++和java中类型,int在c++两个字节,在java占四个字节,这可能会导致push(int)值过大,但在方法2(c++)中把int改为long(4字节),编译仍不通过

3) 上面这个问题研究了很长一段时间,目前还没搞明白,大家看到这篇博客欢迎来探讨、指正

参考推荐:

Leetcode 130: Surrounded Regions

Surrounded Regions

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2013年04月14日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档