Surrounded Regions

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.

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

Analysis

见reference

Code

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;
        int row = board.length;
        int col = board[0].length;

        //走一圈边框，每找到一个O，把它和与之相邻的O都标记为U，表示unflippable
        for (int j=0; j<col; j++){
            if (board[0][j]=='O') markUnflippable(board,0,j);
        }
        for (int j=0; j<col; j++){
            if (board[row-1][j]=='O') markUnflippable(board,row-1,j);
        }
        for (int i=0; i<row; i++){
            if (board[i][0]=='O') markUnflippable(board,i,0);
        }
        for (int i=0; i<row; i++){
            if (board[i][col-1]=='O') markUnflippable(board,i,col-1);
        }

        //modify the board
        for (int i=0; i<row; i++){
            for (int j=0; j<col; j++){
                if (board[i][j]=='O') board[i][j]='X';
                else if (board[i][j]=='U') board[i][j]='O';
            }
        }
    }

    private 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]));}
                }

            }
        }
}

Node

• ArrayDeque: resizable-array implementation of the deque interface. Array deques have no capacity restrictions; they grow as necessary to support usage.

Reference

Leetcode