# 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;
    }
}
```
