Monday, November 24, 2014

[LeetCode] Surrounded Regions

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



思路:

这题题意也略显含糊,实际上就是要将所有以O组成、但不连通到网格边缘的区域变为X。所以我们可以先在四边上寻找连通到边缘的区域,将它们的O都变成Y。剩余的所有O一定无法连通到边缘,所以可以全部变为X。最后再将所有Y变回O。

这题的测试比较tricky,上来没多想就用递归的DFS实现flood fill,结果发现run time error,栈溢出了:


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public:
    void solve(vector<vector<char>> &board) {
        if(board.size()<3 || board[0].size()<3) return;
        fillBorders(board, 'O', 'Y');
        replace(board, 'O', 'X');
        fillBorders(board, 'Y', 'O');
    }
    
    void fill(vector<vector<char>> &board, int i, int j, char target, char c) {
        int m = board.size(), n = board[0].size();
        if(i<0 || j<0 || i>=m || j>=n || board[i][j]!=target) return;
        board[i][j] = c;
        fill(board, i-1, j, target, c);
        fill(board, i+1, j, target, c);
        fill(board, i, j-1, target, c);
        fill(board, i, j+1, target, c);
    }
    
    void fillBorders(vector<vector<char>> &board, char target, char c) {
        int m = board.size(), n = board[0].size();
        for(int i=0; i<m; i++) {
            if(board[i][0]==target) fill(board, i, 0, target, c);
            if(board[i][n-1]==target) fill(board, i, n-1, target, c);
        }
        
        for(int j=1; j<n-1; j++) {
            if(board[0][j]==target) fill(board, 0, j, target, c);
            if(board[m-1][j]==target) fill(board, m-1, j, target, c);
        }
    }
    
    
    void replace(vector<vector<char>> &board, char target, char c) {
        int m = board.size(), n = board[0].size();
        for(int i=0; i<m; i++) {
            for(int j=0; j<n; j++) {
                if(board[i][j]==target)
                    board[i][j] = c;
            }
        }
    }
};


于是些了个迭代版的DFS,果然过了大数据测试。当然这里也可以用BFS实现flood fill。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
public:
    void solve(vector<vector<char>> &board) {
        if(board.size()<3 || board[0].size()<3) return;
        fillBorders(board, 'O', 'Y');
        replace(board, 'O', 'X');
        fillBorders(board, 'Y', 'O');
    }
    
    void fill(vector<vector<char>> &board, int i, int j, char target, char c) {
        int m = board.size(), n = board[0].size();
        if(i<0 || j<0 || i>=m || j>=n || board[i][j]!=target) return;
        stack<pair<int,int>> s;
        s.push(make_pair(i,j));
        
        while(!s.empty()) {
            i = s.top().first;
            j = s.top().second;
            s.pop();
            board[i][j] = c;
            if(i>0 && board[i-1][j]==target) s.push(make_pair(i-1,j));
            if(i<m-1 && board[i+1][j]==target) s.push(make_pair(i+1,j));
            if(j>0 && board[i][j-1]==target) s.push(make_pair(i,j-1));
            if(j<n-1 && board[i][j+1]==target) s.push(make_pair(i,j+1));
        }
    }
    
    void fillBorders(vector<vector<char>> &board, char target, char c) {
        int m = board.size(), n = board[0].size();
        for(int i=0; i<m; i++) {
            if(board[i][0]==target) fill(board, i, 0, target, c);
            if(board[i][n-1]==target) fill(board, i, n-1, target, c);
        }
        
        for(int j=1; j<n-1; j++) {
            if(board[0][j]==target) fill(board, 0, j, target, c);
            if(board[m-1][j]==target) fill(board, m-1, j, target, c);
        }
    }
    
    
    void replace(vector<vector<char>> &board, char target, char c) {
        int m = board.size(), n = board[0].size();
        for(int i=0; i<m; i++) {
            for(int j=0; j<n; j++) {
                if(board[i][j]==target)
                    board[i][j] = c;
            }
        }
    }
};



5 comments:

  1. 楼主是怎么想到想变为Y的?我一看以为这题跟岛屿数是一样的,结果就栈溢出了。

    ReplyDelete
  2. This comment has been removed by the author.

    ReplyDelete
  3. This comment has been removed by the author.

    ReplyDelete
  4. 代码太长这里贴不下。。请问这样写,不考虑大数据的话,和你的方法有什么区别吗?https://github.com/karenpeng/leetCode/blob/64288cbefd090a2a4f3e04a3dcda70071a8a1b93/DFS/surrounded_regions.js#L52

    ReplyDelete
  5. 最后
    replace(board, 'Y', 'O'); 就够了, 不需要 fillBorders

    ReplyDelete