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
class Solution {
private static int rows = 0;
private static int cols = 0;
private static Queue<Integer> queue = null;
private static char[][] myboard;
public void solve(char[][] board) {
if (board == null) {
return;
}
if (board.length == 0 || board[0].length == 0) {
return;
}
myboard = board;
queue = new LinkedList<Integer>();
rows = myboard.length;
cols = myboard[0].length;
for (int i = 0; i < rows; i++) {
putQueue(0,i);
putQueue(cols - 1,i);
}
for (int j = 1; j < cols - 1; j++) {
putQueue(j,0);
putQueue(j,rows - 1);
}
while (!queue.isEmpty()) {
int position = queue.poll();
int x = position % cols, y = position / cols;
if (myboard[y][x] == 'O') {
myboard[y][x] = 'D';
}
putQueue(x - 1, y);
putQueue(x + 1, y);
putQueue(x, y - 1);
putQueue(x, y + 1);
}
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (myboard[i][j] == 'O') {
myboard[i][j] = 'X';
} else if (myboard[i][j] == 'D') {
myboard[i][j] = 'O';
}
}
}
}
public void putQueue(int x, int y) {
if (0 <= x && x < cols && 0 <= y && y < rows && myboard[y][x] == 'O') {
queue.offer(y * cols + x);
}
}
}另外计算xy的位置的时候，不要弄错了
Surrounded Regions LeetCode ：My Solution
原文：http://blog.csdn.net/aresgod/article/details/39901747