Problem:
Given a 2D board containing 'X' and 'O' (the letter 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
/**
* Created by sunny on 7/24/17.
*/
import java.util.*;
public class Solution {
public void solve(char[][] board) {
if (board == null || board.length == 0) {
return;
}
//首先将第一列和最后一列的O变为#
for(int i = 0;i<board.length;i++){
//这是按行遍历
fill(board, i, 0);
fill(board, i, board[i].length-1);
}
//将第一行和最后一行的O变为#
for (int i = 0; i < board[0].length; i++) {
fill(board, 0, i);
fill(board, board.length-1, i);
}
//遍历整个数组，o变为X，#变为O
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[i].length; j++) {
if (board[i][j] == 'O') {
board[i][j] = 'X';
}else if(board[i][j] == '#'){
board[i][j] ='O';
}
}
}
}
private void fill(char[][] board,int row,int col) {
if (board[row][col] == 'X') {
return ;
}
board[row][col] = '#';
Queue<Integer> queue = new LinkedList<>();
//需要将元素的位置存储到 队列中 行和列
int code = row * board[0].length + col;
queue.add(code);
while(!queue.isEmpty()){
//找到这个元素
int temp = queue.poll();
//第几行
int i = temp/board[0].length;
//第几列
int j = temp%board[0].length;
//看这个元素的四个周是不是O,上边
if(i-1>=0&&board[i-1][j] == 'O'){
board[i-1][j] = '#';
queue.add((i-1)*board[0].length+j);
}
if (i+1<board.length&&board[i+1][j] == 'O') {
board[i+1][j] = '#';
queue.add((i+1)*board[0].length+j);
}
if (j-1>=0&&board[i][j-1] == 'O') {
board[i][j-1] = '#';
queue.add(i*board[0].length+j-1);
}
if (j+1<board[0].length&&board[i][j+1]=='O') {
board[i][j+1] = '#';
queue.add(i*board[0].length+j+1);
}
}
} public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
char[][] board = new char[][]{
{'X','X','X','X'},
{'X','O','O','O'},
{'X','O','X','X'},
{'X','X','X','X'}
};
Solution solution = new Solution();
solution.solve(board);
for(int i=0;i<board.length;i++){
for(int j=0;j<board[i].length;j++){
System.out.print(board[i][j]);
}
System.out.println();
}
}
}
采用广度优先遍历求解。---队列的应用