130. Surrounded Regions

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]));
    }
    }
    }
    }
谢谢你,可爱的朋友。