包围的区域

问题

给定一个2D的棋盘,含有‘X’和’O’,找到所有被‘X’包围的’O’,然后把该区域的‘O’都变成’X’。

例子-输入:
X X X X

X O O X
X X O X
X O X X

应该输出:

X X X X
X X X X
X X X X
X O X X

public void solve(char[][] board) {
}

分析:
为了提高效率,我使用了一个mark数组来记录所有访问过的‘O’点,避免重复检查,同时要避免死循环。
每个点有四种状态,未检测(0),正在检测(-1),包围的点(1),没有被包围的点(2)。
另外,为了对付很大的棋盘,避免使用递归而造成堆栈溢出,使用了一个检测队列。

代码如下:

public class SurroundedRegions {

private char[][] board;
private int[][] mark;
private int h;
private int w;

private final int S = 1; //surrounded point
private final int NS = 2; //Not surrounded point
private final int T = -1; //testing point, undetermined point

private static class Point{
int x,y;

Point(int x,int y){
this.x =x;
this.y = y;
}
}

private int test(int i,int j, List<Point> lp){
int result = S;
mark[i][j] = T;
if(i==0 || i==h-1 || j==0 || j==w-1){ //border point
result = NS;
}
else{
int[] nx={i-1,i,i,i+1};
int[] ny={j,j-1,j+1,j};
for(int k=0;k<4;++k){ //check the four directions
int x = nx[k];
int y = ny[k];
if(board[x][y]==’O’){
int m = mark[x][y];
if(m==0){
mark[x][y] = T; //mark as testing point to avoid duplicated visit
lp.add(new Point(x,y));
}
else if(m>0){
result =  m;
}
}
if(result==NS){
break;
}
}
}
mark[i][j]= result;
return result;
}

public void solve(char[][] board) {
this.h = board.length;
if(h<1){
return;
}
this.w = board[0].length;

this.board = board;
this.mark = new int[h][w];

for(int i=0;i<h;++i){
char[] row = board[i];
int[] mrow = mark[i];
for(int j=0;j<w;++j){
char c = row[j];
if(c==’O’ && mrow[j]==0){ //not marked point
List<Point> lp = new ArrayList<Point>(); //visit queue
lp.add(new Point(i,j));
int result = S;
for(int k=0;k<lp.size();++k){ //Notice: the size of queue maybe increase during the loop
Point p = lp.get(k);
if(test(p.x,p.y,lp) == NS){ //once find the NS flag,stop checking
result = NS;
break;
}
}
for(int k=0;k<lp.size();++k){ //mark  all points in the current visit queue
Point p = lp.get(k);
mark[p.x][p.y] = result;
}
}
}
}
for(int i=0;i<h;++i){ //flip all marked points
char[] row = board[i];
int[] mrow = mark[i];
for(int j=0;j<w;++j){
char c = row[j];
if(c==’O’ && mrow[j]==S){
row[j] =’X’;
}
}
}
}

====update====
改进了一下,从边开始扫描,找到所有边上白字相邻的节点即可解决问题。代码如下:

public class SurroundedRegions {

private char[][] board;
private int[][] mark;
private int h;
private int w;

private static class Point {
int x, y;

Point(int x, int y) {
this.x = x;
this.y = y;
}
}

private List<Point> extend(int i, int j) {
List<Point> lp = new ArrayList<Point>();
int[] nx = { i – 1, i, i, i + 1 };
int[] ny = { j, j – 1, j + 1, j };
for (int k = 0; k < 4; ++k) { // check the four directions
int x = nx[k];
int y = ny[k];
if (x >= 0 && x < h && y >= 0 && y < w && board[x][y] == ‘O’ && mark[x][y] == 0) {
mark[x][y] = 1;
lp.add(new Point(x, y));
}
}
return lp;
}

public void solve(char[][] board) {
this.h = board.length;
if (h <= 1) {
return;
}
this.w = board[0].length;

this.board = board;
this.mark = new int[h][w];

int x = 0, y = 0;
int[] dxx = { 1, 0, -1, 0 };
int[] dyy = { 0, 1, 0, -1 };

for (int i = 0; i < 4; ++i) {
int dx = dxx[i];
int dy = dyy[i];
int len = (i % 2 == 0) ? h : w;
for (int j = 0; j < len-1; ++j) {
char c = board[x][y];
if (c == ‘O’ && mark[x][y] == 0) {
List<Point> vq = new ArrayList<Point>(); // visit queue
vq.add(new Point(x, y));
while (!vq.isEmpty()) {
Point p = vq.remove(vq.size() – 1);
mark[p.x][p.y] = 1;
vq.addAll(extend(p.x, p.y));
}
}
x += dx;
y += dy;
}
}

for (int i = 0; i < h; ++i) { // flip all unmarked points
char[] row = board[i];
int[] mrow = mark[i];
for (int j = 0; j < w; ++j) {
char c = row[j];
if (c == ‘O’ && mrow[j] == 0) {
row[j] = ‘X’;
}
}
}
}
}

标签