# Surrounded Regions

## 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.

**Example**

```
X X X X
X O O X
X X O X
X O X X
```

After capture all regions surrounded by 'X', the board should be:

```
X X X X
X X X X
X X X X
X O X X
```

**Tags**

Breadth First Search Union Find

**Related Problems**

Hard Number of Islands II\
Easy Number of Islands

## Analysis

本题也是一个多解的问题。

一种比较巧妙的思路是从边缘的'O'出发，通过DFS，所有能够遍历的'O'都可以暂时被标记为'#'，那么剩下未能被标记的'O'说明被surrounded，需要在遍历结束之后全部转为'X'。（用DFS或者BFS要警惕栈溢出）

另一种方法是用Union Find，将与边缘相连通的'O'全部union到一个dummy node（也可以用hasEdge\[]来存储，不过内存占用更多）, 最终将没有和这个dummy node是一个component的'O'点全部标记为'X'。

## Solution

DFS - (7ms AC 42.74%)

```java
class Solution {
    public void solve(char[][] board) {
        if (board == null || board.length == 0 || board[0].length == 0) return;
        int m = board.length;
        int n = board[0].length;

        // Marking 'O' on the boundary and connected as '*'
        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'O') {
                marking(board, i, 0);
            }
            if (board[i][n - 1] == 'O') {
                marking(board, i, n - 1);
            }
        }
        for (int j = 0; j < n; j++) {
            if (board[0][j] == 'O') {
                marking(board, 0, j);
            }
            if (board[m - 1][j] == 'O') {
                marking(board, m - 1, j);
            }
        }

        // Replacing 'O' as 'X'
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
            }
        }

        // Replacing '*' as 'X'
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == '*') {
                    board[i][j] = 'O';
                }
            }
        }

    }

    // DFS marking 'O' as '*'
    private void marking (char[][] board, int x, int y) {
        int[] dx = {0, 1, 0, -1};
        int[] dy = {1, 0, -1, 0};
        int nx, ny;
        if (board[x][y] == 'O') {
            board[x][y] = '*';
            for (int i = 0; i < 4; i++) {
                nx = x + dx[i]; 
                ny = y + dy[i];
                if (nx >= 0 && ny >= 0 && nx < board.length && ny < board[0].length) {
                    marking(board, nx, ny);
                }
            } 
        }
    }
}
```

DFS - (4ms AC 100%)

```java
class Solution {
    public void solve(char[][] board) {

        if (board.length < 1 || board[0].length < 1)
            return;
        for (int i = 0; i < board.length; i++) {
            if (board[i][0] != 'X');
            dfsmarker(i, 0, board);
        }
        for (int i = 0; i < board.length; i++) {
            if (board[i][board[0].length - 1] != 'X')
                dfsmarker(i, board[0].length - 1, board);
        }
        for (int j = 0; j < board[0].length; j++) {
            if (board[0][j] != 'X');
            dfsmarker(0, j, board);
        }
        for (int j = 0; j < board[0].length; j++) {
            if (board[board.length - 1][j] != 'X')
                dfsmarker(board.length - 1, j, board);
        }
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                //System.out.println(marker[i][j]);
                if (board[i][j] == 'M')
                    board[i][j] = 'O';
                else
                    board[i][j] = 'X';
            }

        }
        //System.out.println(marker[1][1]);
        return;


    }
    public void dfsmarker(int i, int j, char[][] board) {
        if (board[i][j] == 'M' || board[i][j] != 'O')
            return;

        board[i][j] = 'M';
        if (i > 0)
            dfsmarker(i - 1, j, board);
        if (j > 0)
            dfsmarker(i, j - 1, board);
        if (i < board.length - 1)
            dfsmarker(i + 1, j, board);
        if (j < board[0].length - 1)
            dfsmarker(i, j + 1, board);
    }

}
```

DFS - Cleaner Version (6ms 59.18%)

```java
class Solution {
    public void solve(char[][] board) {
        if (board.length == 0 || board[0].length == 0) return;
        if (board.length < 3 || board[0].length < 3) return;
        int m = board.length;
        int n = board[0].length;
        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'O') helper(board, i, 0);
            if (board[i][n - 1] == 'O') helper(board, i, n - 1);
        }
        for (int j = 1; j < n - 1; j++) {
            if (board[0][j] == 'O') helper(board, 0, j);
            if (board[m - 1][j] == 'O') helper(board, m - 1, j);
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') board[i][j] = 'X';
                if (board[i][j] == '*') board[i][j] = 'O';
            }
        }
    }

    private void helper(char[][] board, int r, int c) {
        if (r < 0 || c < 0 || r > board.length - 1 || c > board[0].length - 1 || board[r][c] != 'O') return;
        board[r][c] = '*';
        helper(board, r + 1, c);
        helper(board, r - 1, c);
        helper(board, r, c + 1);
        helper(board, r, c - 1);
    }
}
```

Union Find (20 ms 14.75% AC)

```java
class UnionFind {
    private int[] id;
    private int[] size;

    public UnionFind(int n) {
        id = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            id[i] = i;
            size[i] = 1;
        }
    }

    public int find(int i) {
        while (i != id[i]) {
            id[i] = id[id[i]];
            i = id[i];
        }
        return i;
    }

    public void union(int x, int y) {
        int i = find(x);
        int j = find(y);
        if (i == j) {
            return;
        }
        if (size[i] < size[j]) {
            id[i] = j;
            size[j] += size[i];
        } else {
            id[j] = i;
            size[i] += size[j];
        }
    }

    public boolean connected(int x, int y) {
        return find(x) == find(y);
    }
}

public class Solution {

    private boolean isEdge(int M, int N, int i, int j) {
        return (i == 0 || i == M - 1 || j == 0 || j == N - 1);
    }

    private boolean insideBoard(int M, int N, int i, int j) {
        return (i < M && i >= 0 && j < N && j >= 0);
    }
    /**
     * @param board a 2D board containing 'X' and 'O'
     * @return void
     */
    public void surroundedRegions(char[][] board) {
        if (board == null || board.length == 0 || board[0].length == 0) {
            return;
        }
        int M = board.length;
        int N = board[0].length;

        int[] dirX = {0, 0, -1, 1};
        int[] dirY = {-1, 1, 0, 0};

        UnionFind uf = new UnionFind(M * N + 1);


        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if (board[i][j] == 'O') {
                    if (isEdge(M, N, i, j)) {
                        uf.union(i * N + j, M * N);
                    } else {
                        for (int k = 0; k < 4; k++) {
                            int x = i + dirX[k];
                            int y = j + dirY[k];
                            if (insideBoard(M, N, x, y) && board[x][y] == 'O') {
                                uf.union(i * N + j, x * N + y);
                            }
                        }
                    }
                }
            }
        }

        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if (!uf.connected(i * N + j, M * N)) {
                    board[i][j] = 'X';
                }
            }
        }

    }
}
```

## Reference

* [LeetCode Discussion: Solve it using Union Find](https://discuss.leetcode.com/topic/1944/solve-it-using-union-find/7)
* [Flood Fill Algorithm](https://en.wikipedia.org/wiki/Flood_fill)
* [水中的鱼 Surrounded Regions, Solution BFS](http://fisherlei.blogspot.com/2013/03/leetcode-surrounded-regions-solution.html)
* [喜刷刷 Surrounded Regions](http://bangbingsyb.blogspot.com/2014/11/leetcode-surrounded-regions.html)
* [programcreek: LeetCode – Surrounded Regions](http://www.programcreek.com/2014/04/leetcode-surrounded-regions-java/)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/union_find/surrounded_regions.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.