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:

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

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