> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/solutions/0130-surrounded-regions.md).

# 0130. Surrounded Regions

<https://leetcode.com/problems/surrounded-regions>

## Description

Given an `m x n` matrix `board` containing `'X'` and `'O'`, *capture all regions that are 4-directionally surrounded by* `'X'`.

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

**Example 1:**

![](https://assets.leetcode.com/uploads/2021/02/19/xogrid.jpg)

```
**Input:** board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
**Output:** [["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
**Explanation:** Surrounded regions should not be on the border, which means that any 'O' on the border of the board are not flipped to 'X'. Any 'O' that is not on the border and it is not connected to an 'O' on the border will be flipped to 'X'. Two cells are connected if they are adjacent cells connected horizontally or vertically.
```

**Example 2:**

```
**Input:** board = [["X"]]
**Output:** [["X"]]
```

**Constraints:**

* `m == board.length`
* `n == board[i].length`
* `1 <= m, n <= 200`
* `board[i][j]` is `'X'` or `'O'`.

## ac1： BFS

It's time consuming, but it's at least original by me.

```java
class Solution {
    boolean savior = false;
    private char[][] grid;
    int gr;
    int gc;
    Stack<int[]> stack;

    public void solve(char[][] board) {
        stack = new Stack<int[]>();
        grid = board;
        if (grid == null) return;
        gr = grid.length;
        if (gr == 0) return;
        gc = grid[0].length;

        Queue<int[]> queue = new LinkedList<int[]>();
        for (int i = 1; i < gr - 1; i++) {
            for (int j = 1; j < gc - 1; j++) {
                if (grid[i][j] == 'O') {
                    queue.offer(new int[]{i,j});
                    Stack<int[]> tmpStack = new Stack<int[]>();
                    while (!queue.isEmpty()) {
                        int[] head = queue.poll();
                        int r = head[0], c = head[1];
                        if (r < 0 || c < 0 || r >= gr || c >= gc || grid[r][c] != 'O'){
                            continue;
                        }
                        if (isSavior(r,c)) savior = true;
                        grid[r][c] = 'X';
                        tmpStack.push(new int[]{r,c});

                        queue.offer(new int[]{r+1,c});
                        queue.offer(new int[]{r-1,c});
                        queue.offer(new int[]{r,c+1});
                        queue.offer(new int[]{r,c-1});
                    }
                    if (savior) {
                        while (!tmpStack.isEmpty()) {
                            stack.push(tmpStack.pop());
                        }
                    }
                    savior = false;
                }
            }
        }

        while (!stack.isEmpty()) {
            int[] head = stack.pop();
            grid[head[0]][head[1]] = 'O';
        }
    }

    private boolean isSavior(int r, int c){
        if (grid[r][c] != 'O') return false;
        return r-1 < 0 || c-1 < 0 || r+1 >= gr || c+1 >= gc;
    }
}
```