Posted on 2013-04-15 18:17
小明 阅读(1556)
评论(2) 编辑 收藏 所属分类:
数据结构和算法
分析：
为了提高效率，我使用了一个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';
}
}
}
}
}