围棋吃子问题

题目：

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

代码：

import java.awt.*;

public class Solution {
    char[][] board;
    int r,c;
    
    public void solve(char[][] board) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(board == null || board.length <= 0)
            return;
            
        this.board = board;
        r = board.length;
        c = board[0].length;
        
        for(int i=0;i<r;i++){
            mark(i,0);
            mark(i,c-1);
        }
        
        for(int i=0;i<c;i++){
            mark(0,i);
            mark(r-1,i);
        }
        
        for(int i=0;i<r;i++){
            for(int j=0;j<c;j++){
                this.board[i][j] = this.board[i][j] == 'O'?'X':this.board[i][j] == 'A'?'O':'X';
            }
        }
    }
    
    private void mark(int x,int y){
        if(x<0 || y<0 || x>=r || y >=c || this.board[x][y] != 'O')
            return;
        
        this.board[x][y] = 'A';
        
        Queue<Point> s = new LinkedList<Point>();
        
        s.add(new Point(x-1,y));
        s.add(new Point(x+1,y));
        s.add(new Point(x,y-1));
        s.add(new Point(x,y+1));
        
        while(!s.isEmpty()){
            Point p = s.poll();
            x = p.x;
            y = p.y;
            if(x<0 || y<0 || x>=r || y >=c || this.board[x][y] != 'O'){
                continue;
            }
            
            this.board[x][y] = 'A';
            s.add(new Point(x-1,y));
            s.add(new Point(x+1,y));
            s.add(new Point(x,y-1));
            s.add(new Point(x,y+1));
        }
    }
}