130. Surrounded Regions

发表于 | 更新于: | 分类于 | 本文总阅读量 次
| 字数统计: 2,745 | 阅读时长 ≈ 17

https://leetcode.com/problems/surrounded-regions/?tab=Description

Given a 2D board containing ‘X’ and ‘O’ (the letter O), capture all regions surrounded by ‘X’.

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

1
2
3
4
5
6
7
8
9
10
11
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

cpp

23ms, 32.42%, October 14, 2016

https://discuss.leetcode.com/topic/17224/a-really-simple-and-readable-c-solution-only-cost-12ms

A really simple and readable C++ solution，only cost 12ms

  • First, check the four border of the matrix. If there is a element is ‘O’, alter it and all its neighbor ‘O’ elements to ‘1’.
  • Then ,alter all the ‘O’ to ‘X’
  • At last,alter all the ‘1’ to ‘O’
1
2
3
4
5
6
For example:

         X X X X           X X X X             X X X X
         X X O X  ->       X X O X    ->       X X X X
         X O X X           X 1 X X             X O X X
         X O X X           X 1 X X             X O X X
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
class Solution {
public:
    void solve(vector<vector<char>>& board) {
        int i, j;
        int row = board.size();
        if(!row) return;
        int col = board[0].size();
        
        for(i=0; i<row; i++){
            check(board, i, 0, row, col);
            if(col>1)
                check(board, i, col-1, row, col);
        }
        
        for(j=1; j+1<col; j++){
            check(board, 0, j, row, col);
            if(row>1)
                check(board, row-1, j, row, col);
        }
        
        for(i=0; i<row; i++)
            for(j=0; j<col; j++)
                if(board[i][j]=='O')
                    board[i][j] = 'X';
        
        for(i=0; i<row; i++)
            for(j=0; j<col; j++)
                if(board[i][j] == '1')
                    board[i][j] = 'O';
    }
    
    void check(vector<vector<char>> &vec, int i, int j, int row, int col){
        if(vec[i][j] == 'O'){
            vec[i][j] = '1';
            if(i>1)
                check(vec, i-1, j, row, col);
            if(j>1)
                check(vec, i, j-1, row, col);
            if(i+1<row)
                check(vec, i+1, j, row, col);
            if(j+1<col)
                check(vec, i, j+1, row, col);
        }
    }
};

https://discuss.leetcode.com/topic/1944/solve-it-using-union-find

Solve it using Union Find

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
class UF
{
private:
	int* id;     // id[i] = parent of i
	int* rank;  // rank[i] = rank of subtree rooted at i (cannot be more than 31)
	int count;    // number of components
public:
	UF(int N)
	{
		count = N;
		id = new int[N];
		rank = new int[N];
		for (int i = 0; i < N; i++) {
			id[i] = i;
			rank[i] = 0;
		}
	}
	~UF()
	{
		delete [] id;
		delete [] rank;
	}
	int find(int p) {
		while (p != id[p]) {
			id[p] = id[id[p]];    // path compression by halving
			p = id[p];
		}
		return p;
	}
	int getCount() {
		return count;
	}
	bool connected(int p, int q) {
		return find(p) == find(q);
	}
	void connect(int p, int q) {
		int i = find(p);
		int j = find(q);
		if (i == j) return;
		if (rank[i] < rank[j]) id[i] = j;
		else if (rank[i] > rank[j]) id[j] = i;
		else {
			id[j] = i;
			rank[i]++;
		}
		count--;
	}
};

class Solution {
public:
    void solve(vector<vector<char>> &board) {
        int n = board.size();
        if(n==0)    return;
        int m = board[0].size();
        UF uf = UF(n*m+1);
        
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if((i==0||i==n-1||j==0||j==m-1)&&board[i][j]=='O') // if a 'O' node is on the boundry, connect it to the dummy node
                    uf.connect(i*m+j,n*m);
                else if(board[i][j]=='O') // connect a 'O' node to its neighbour 'O' nodes
                {
                    if(board[i-1][j]=='O')
                        uf.connect(i*m+j,(i-1)*m+j);
                    if(board[i+1][j]=='O')
                        uf.connect(i*m+j,(i+1)*m+j);
                    if(board[i][j-1]=='O')
                        uf.connect(i*m+j,i*m+j-1);
                    if(board[i][j+1]=='O')
                        uf.connect(i*m+j,i*m+j+1);
                }
            }
        }
        
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(!uf.connected(i*m+j,n*m)){ // if a 'O' node is not connected to the dummy node, it is captured
                    board[i][j]='X';
                }
            }
        }
    }
};

Hi. So here is my accepted code using Union Find data structure. The idea comes from the observation that if a region is NOT captured, it is connected to the boundry. So if we connect all the ‘O’ nodes on the boundry to a dummy node, and then connect each ‘O’ node to its neighbour ‘O’ nodes, then we can tell directly whether a ‘O’ node is captured by checking whether it is connected to the dummy node.

For more about Union Find, the first assignment in the algo1 may help:

https://www.coursera.org/course/algs4partI

https://discuss.leetcode.com/topic/1944/solve-it-using-union-find/2

just another version in java:

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
public class Solution {
    
    int[] unionSet; // union find set
    boolean[] hasEdgeO; // whether an union has an 'O' which is on the edge of the matrix
    
    public void solve(char[][] board) {
        if(board.length == 0 || board[0].length == 0) return;
        
        // init, every char itself is an union
        int height = board.length, width = board[0].length;
        unionSet = new int[height * width];
        hasEdgeO = new boolean[unionSet.length];
        for(int i = 0;i<unionSet.length; i++) unionSet[i] = i;
        for(int i = 0;i<hasEdgeO.length; i++){
            int x = i / width, y = i % width;
            hasEdgeO[i] = (board[x][y] == 'O' && (x==0 || x==height-1 || y==0 || y==width-1));
        }
        
        // iterate the matrix, for each char, union it + its upper char + its right char if they equals to each other
        for(int i = 0;i<unionSet.length; i++){
            int x = i / width, y = i % width, up = x - 1, right = y + 1;
            if(up >= 0 && board[x][y] == board[up][y]) union(i,i-width);
            if(right < width && board[x][y] == board[x][right]) union(i,i+1);
        }
        
        // for each char in the matrix, if it is an 'O' and its union doesn't has an 'edge O', the whole union should be setted as 'X'
        for(int i = 0;i<unionSet.length; i++){
            int x = i / width, y = i % width;
            if(board[x][y] == 'O' && !hasEdgeO[findSet(i)]) 
                board[x][y] = 'X'; 
        }
    }
    
    private void union(int x,int y){
        int rootX = findSet(x);
        int rootY = findSet(y);
        // if there is an union has an 'edge O',the union after merge should be marked too
        boolean hasEdgeO = this.hasEdgeO[rootX] || this.hasEdgeO[rootY];
        unionSet[rootX] = rootY;
        this.hasEdgeO[rootY] = hasEdgeO;
    }
    
    private int findSet(int x){
        if(unionSet[x] == x) return x;
        unionSet[x] = findSet(unionSet[x]);
        return unionSet[x];
    }
}

https://discuss.leetcode.com/topic/18706/9-lines-python-148-ms

9 lines, Python 148 ms

Phase 1: “Save” every O-region touching the border, changing its cells to ‘S’.

Phase 2: Change every ‘S’ on the board to ‘O’ and everything else to ‘X’.

1
2
3
4
5
6
7
8
9
10
11
12
def solve(self, board):
    if not any(board): return

    m, n = len(board), len(board[0])
    save = [ij for k in range(m+n) for ij in ((0, k), (m-1, k), (k, 0), (k, n-1))]
    while save:
        i, j = save.pop()
        if 0 <= i < m and 0 <= j < n and board[i][j] == 'O':
            board[i][j] = 'S'
            save += (i, j-1), (i, j+1), (i-1, j), (i+1, j)

    board[:] = [['XO'[c == 'S'] for c in row] for row in board]

In case you don’t like my last line, you could do this instead:

1
2
3
for row in board:
    for i, c in enumerate(row):
        row[i] = 'XO'[c == 'S']

https://discuss.leetcode.com/topic/2982/my-bfs-solution-c-28ms

My BFS solution (C++ 28ms)

The algorithm is quite simple: Use BFS starting from ‘O’s on the boundary and mark them as ‘B’, then iterate over the whole board and mark ‘O’ as ‘X’ and ‘B’ as ‘O’.

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
52
53
54
55
56
57
58
59
60
61
62
63
64
void bfsBoundary(vector<vector<char> >& board, int w, int l)
{
    int width = board.size();
    int length = board[0].size();
    deque<pair<int, int> > q;
    q.push_back(make_pair(w, l));
    board[w][l] = 'B';
    while (!q.empty()) {
        pair<int, int> cur = q.front();
        q.pop_front();
        pair<int, int> adjs[4] = {{cur.first-1, cur.second}, 
            {cur.first+1, cur.second}, 
            {cur.first, cur.second-1},
            {cur.first, cur.second+1}};
        for (int i = 0; i < 4; ++i)
        {
            int adjW = adjs[i].first;
            int adjL = adjs[i].second;
            if ((adjW >= 0) && (adjW < width) && (adjL >= 0)
                    && (adjL < length) 
                    && (board[adjW][adjL] == 'O')) {
                q.push_back(make_pair(adjW, adjL));
                board[adjW][adjL] = 'B';
            }
        }
    }
}

void solve(vector<vector<char> > &board) {
    int width = board.size();
    if (width == 0) //Add this to prevent run-time error!
        return;
    int length = board[0].size();
    if  (length == 0) // Add this to prevent run-time error!
        return;

    for (int i = 0; i < length; ++i)
    {
        if (board[0][i] == 'O')
            bfsBoundary(board, 0, i);

        if (board[width-1][i] == 'O')
            bfsBoundary(board, width-1, i);
    }

    for (int i = 0; i < width; ++i)
    {
        if (board[i][0] == 'O')
            bfsBoundary(board, i, 0);
        if (board[i][length-1] == 'O')
            bfsBoundary(board, i, length-1);
    }

    for (int i = 0; i < width; ++i)
    {
        for (int j = 0; j < length; ++j)
        {
            if (board[i][j] == 'O')
                board[i][j] = 'X';
            else if (board[i][j] == 'B')
                board[i][j] = 'O';
        }
    }
}

Note that one of the test cases is when the board is empty. So if you don’t check it in your code, you will encounter an run-time error.

https://discuss.leetcode.com/topic/25010/java-dfs-boundary-cell-turning-solution-simple-and-clean-code-commented

Java DFS + boundary cell turning solution, simple and clean code, commented.

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
public void solve(char[][] board) {
	if (board.length == 0 || board[0].length == 0)
		return;
	if (board.length < 2 || board[0].length < 2)
		return;
	int m = board.length, n = board[0].length;
	//Any 'O' connected to a boundary can't be turned to 'X', so ...
	//Start from first and last column, turn 'O' to '*'.
	for (int i = 0; i < m; i++) {
		if (board[i][0] == 'O')
			boundaryDFS(board, i, 0);
		if (board[i][n-1] == 'O')
			boundaryDFS(board, i, n-1);	
	}
	//Start from first and last row, turn '0' to '*'
	for (int j = 0; j < n; j++) {
		if (board[0][j] == 'O')
			boundaryDFS(board, 0, j);
		if (board[m-1][j] == 'O')
			boundaryDFS(board, m-1, j);	
	}
	//post-prcessing, turn 'O' to 'X', '*' back to 'O', keep 'X' intact.
	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] == '*')
				board[i][j] = 'O';
		}
	}
}
//Use DFS algo to turn internal however boundary-connected 'O' to '*';
private void boundaryDFS(char[][] board, int i, int j) {
	if (i < 0 || i > board.length - 1 || j <0 || j > board[0].length - 1)
		return;
	if (board[i][j] == 'O')
		board[i][j] = '*';
	if (i > 1 && board[i-1][j] == 'O')
		boundaryDFS(board, i-1, j);
	if (i < board.length - 2 && board[i+1][j] == 'O')
		boundaryDFS(board, i+1, j);
	if (j > 1 && board[i][j-1] == 'O')
		boundaryDFS(board, i, j-1);
	if (j < board[i].length - 2 && board[i][j+1] == 'O' )
		boundaryDFS(board, i, j+1);
}

https://discuss.leetcode.com/topic/6496/my-java-o-n-2-accepted-solution

My Java O(n^2) accepted solution

The idea is pretty simple: a ‘O’ marked cell cannot be captured whether:

  1. It is in contact with the border of the board or
  2. It is adjacent to an unflippable cell.

So the algorithm is straightforward:

  1. Go around the border of the board
  2. When a ‘O’ cell is found mark it with ‘U’ and perform a DFS on its adjacent cells looking for other ‘O’ marked cells.
  3. When the entire border is processed scan again the board
  • If a cell is marked as ‘O’ it wasn’t connected to unflippable cell. Hence capture it with ‘X’
  • If a cell is marked as ‘X’ nothing must be done.

  • If a cell is marked as ‘U’ mark it as ‘O’ because it was an original ‘O’ marked cell which satisfied one of the above conditions.
    On a technical side regarding the code:

  • In the problem statement it’s not specified that the board is rectangular. So different checks must performed when scanning the border.

  • Since a pure recursive search causes stack overflow it’s necessary to make the DFS iterative using a stack to simulate recursion.
    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
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    public class Solution {
        static class Pair {
        public int first;
        public int second;
        public Pair(int f, int s) {
            first = f;
            second = s;
        }
    }

    public void solve(char[][] board) {
        if(board == null || board.length == 0) {
            return ;
        }
        for(int i = 0; i < board[0].length; ++i) {
            if(board[0][i] == 'O') {
                markUnflippable(board,0,i);
            }
        }
        for(int i = 0; i < board[board.length-1].length; ++i) {
            if(board[board.length-1][i] == 'O') {
                markUnflippable(board,board.length-1,i);
            }
        }
        for(int i = 0 ; i < board.length; ++i) {
            if(board[i][0] == 'O') {
                markUnflippable(board,i,0);
            }
        }
        for(int i =0; i < board.length; ++i) {
            if(board[i][board[i].length-1] == 'O') {
                markUnflippable(board,i,board[i].length-1);
            }
        }
        
        // modify the board
        for(int i = 0; i < board.length; ++i) {
            for(int j = 0; j < board[i].length; ++j) {
                if(board[i][j] == 'O') {
                    board[i][j] = 'X';
                } else if(board[i][j] == 'U') {
                    board[i][j] = 'O';
                }
            }
        }
    }

    public void markUnflippable(char[][] board, int r, int c) {
        int[] dirX = {-1,0,1,0};
        int[] dirY = {0,1,0,-1};
        ArrayDeque<Pair> stack = new ArrayDeque<>();
        stack.push(new Pair(r,c));
        while(!stack.isEmpty()) {
            Pair p = stack.pop();
            board[p.first][p.second] = 'U';
            for(int i = 0; i < dirX.length; ++i) {
                if(p.first + dirX[i] >= 0 && p.first + dirX[i] < board.length && p.second + dirY[i] >= 0 && p.second +dirY[i] < board[p.first + dirX[i]].length && board[p.first+dirX[i]][p.second+dirY[i]] == 'O') {
                    stack.push(new Pair(p.first+dirX[i],p.second+dirY[i]));
                }
            }
        }
    }
谢谢你，可爱的朋友。