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

这道题就是利用BFS来找到所有不touch边界的o的集合,然后将其设为X。
但是如果直接找的话必须要把所有找到的点都存起来,太浪费空间。
我们的做法是先将边缘扫一遍,只要发现O的就放进FIFO中,并标记为“Y”,然后BFS把所有相邻的O都标记为Y,最后只要整个扫一遍将没有标记为Y的O设为X,然后将Y改回O即可。

public class Solution {
    public void solve(char[][] board) {
        if (board.length == 0)
            return;
            
        Queue<Integer> bfs = new LinkedList<Integer> ();
        //start and end row
        for (int i = 0; i < board[0].length; i++)
        {
            if(board[0][i] == 'O')
            {
                bfs.add(0);
                bfs.add(i);
                board[0][i] = 'Y';
            }
            if (board[board.length - 1][i] == 'O')
            {
                bfs.add(board.length - 1);
                bfs.add(i);
                board[board.length-1][i] = 'Y';
            }
        }
        //start and end column
        for(int i = 0; i < board.length; i++)
        {
            if (board[i][0] == 'O')
            {
                bfs.add(i);
                bfs.add(0);
                board[i][0] = 'Y';
            }
            if (board[i][board[0].length - 1] == 'O')
            {
                bfs.add(i);
                bfs.add(board[0].length - 1);
                
                board[i][board[0].length-1] = 'Y';
            }
        }
        // mark all O reigon that is connected to the boarder to Y 
        while(!bfs.isEmpty())
        {
            int r = bfs.remove();
            int c = bfs.remove();
            
            if (r + 1 < board.length)
            {
               if (board[r+1][c] == 'O')
                {
                    bfs.add(r+1);
                    bfs.add(c);
                    board[r+1][c] = 'Y';
                } 
            }
            
            if (r - 1 >= 0)
            {
                if (board[r-1][c] == 'O')
                {
                        bfs.add(r-1);
                        bfs.add(c);
                        board[r-1][c] = 'Y';
                }
            }
            
            if (c + 1 < board[0].length)
            {
                if (board[r][c+1] == 'O')
                {
                    bfs.add(r);
                    bfs.add(c+1);
                    board[r][c+1] = 'Y';
                }
            }
            
            if (c - 1 >= 0)
            {
                if (board[r][c-1] == 'O')
                {
                    bfs.add(r);
                    bfs.add(c-1);
                    board[r][c - 1] = 'Y';
                }
            }
        }
        
        for (int i = 1; i < board.length-1; i++)
        {
            for (int j = 1; j < board[0].length-1; j++)
            {
                if (board[i][j] == 'O')
                    board[i][j] = 'X';
            }
        }
        
        for (int i = 0; i < board.length; i++)
        {
            for (int j = 0; j < board[0].length; j++)
            {
                if (board[i][j] == 'Y')
                    board[i][j] = 'O';
            }
        }
        
    }
}

Recursive BFS, notice when doing BFS mark visited when vertex is enqueue, dont wait until vertex dequeue to avoid duplicate enqueue.

public class Solution {
    public void solve(char[][] board) {
        if (board.length == 0 || board.length == 1 || board[0].length == 1) 
            return;
        int rowLen = board.length;
        int colLen = board[0].length;    
        for (int i = 0; i < colLen; i++) {
            if (board[0][i] == 'O')
                BFSMark(board, 0, i, 'Y', 'O');
            if (board[rowLen-1][i] == 'O') 
                BFSMark(board, rowLen-1, i, 'Y', 'O');
        }
        for (int i = 0; i < rowLen; i++) {
            if (board[i][0] == 'O')
                BFSMark(board, i, 0, 'Y', 'O');
            if (board[i][colLen - 1] == 'O')
                BFSMark(board, i, colLen - 1, 'Y', 'O');
        }
        
        for (int r = 0; r < rowLen; r++) {
            for (int c = 0; c < colLen; c++) {
                if (board[r][c] == 'O') {
                    board[r][c] = 'X';
                }
            }
        }
        
        for (int r = 0; r < rowLen; r++) {
            for (int c = 0; c < colLen; c++) {
                if (board[r][c] == 'Y') {
                   board[r][c] = 'O';
                }
            }
        }
        
    }
    
    public void BFSMark(char [][] board, int r, int c, char ch, char t) {
        LinkedList<Integer> rowVisited = new LinkedList<Integer>();
        LinkedList<Integer> colVisited = new LinkedList<Integer>();
        rowVisited.add(r);
        colVisited.add(c);
        int rowLen = board.length;
        int colLen = board[0].length;
        while(!rowVisited.isEmpty()) {
            int currRow = rowVisited.removeFirst();
            int currCol = colVisited.removeFirst();
            board[currRow][currCol] = ch;
            if (currRow + 1 < rowLen) {
                if (board[currRow + 1][currCol] == t) {
                    rowVisited.add(currRow+1);
                    colVisited.add(currCol);
                    board[currRow+1][currCol] = ch; //mark visited when entering queue
                }
            }
            if (currRow - 1 >= 0) {
                if (board[currRow - 1][currCol] == t) {
                    rowVisited.add(currRow-1);
                    colVisited.add(currCol);
                    board[currRow-1][currCol] = ch; //mark visited when entering queue
                }
            }
            if (currCol + 1 < colLen) {
                if (board[currRow][currCol + 1] == t) {
                    rowVisited.add(currRow);
                    colVisited.add(currCol+1);
                    board[currRow][currCol+1] = ch; //mark visited when entering queue
                }
            }
            if (currCol - 1 >= 0) {
                if (board[currRow][currCol - 1] == t) {
                    rowVisited.add(currRow);
                    colVisited.add(currCol-1);
                    board[currRow][currCol-1] = ch; //mark visited when entering queue
                }
            }
        }
    }
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s