学步园

  之前都在poj玩，第一次刷LeetCode OJ的题目，求Surrounded Regions。原题http://oj.leetcode.com/problems/surrounded-regions/ 。

  我一开始想用DP推导， board[i][j] = surrounded if{ board[i+_1][j+-1] ==' x' or  board[i+_1][j+-1] got surrounded too}，但是发现第二个条件很难判定。

  然后再想起，任何一个O如果它没有被X包围，那么它一定和最外面的边界的某个O是连通的。反过来，也就是可以从最外面那层所有的O开始用广度搜索所有没有被包围的O。

  PS下，一开始我直接用递归来广搜，但是当测试数据上到250*250矩阵后，直接递归导致的空间太大直接runtime error。然后改为用个Stack来搜索就ac了。

  刷题这种东西还是讲状态，刚看到这题时候想着20分钟就能搞定，结果各种小bug。。。。。。。。。。。。

  直接上代码,包括递归和非递归版本:

import java.lang.reflect.Array;
import java.io.*;


public class Solution {
	
	public void solve(char[][] board)
	{
		if(board==null)
			return;
		int row=board.length;
		if(row == 0)
			return;
		int col=board[0].length;
		if(col == 0)
			return;
		
		boolean[][] vFlag = new boolean[row][col];
		boolean[][] sFlag = new boolean[row][col];
		for(int i=0;i<row;i++)
		{
			for(int j=0;j<col;j++)
			{
				sFlag[i][j] = true;
				vFlag[i][j] = false;
			}
		}
		
//		java.util.ArrayList<Integer> orIndex = new java.util.ArrayList<Integer>();
//		java.util.ArrayList<Integer> ocIndex = new java.util.ArrayList<Integer>();
		for(int i=0;i<row;i++)
		{
			if(board[i][0] == 'O')
			{
				if(vFlag[i][0] == false)
				{
					TraverNeighorhood_Breath( board, vFlag, sFlag, i, 0, row, col);
				}
			}
			if(board[i][col-1] == 'o'|| board[i][col-1] == 'O')
			{
				if(vFlag[i][col-1] == false)
				{
					TraverNeighorhood_Breath( board, vFlag, sFlag, i, col-1, row, col);
				}
			}
		}
		
		for(int j=1;j<col-1;j++)
		{
			if(board[0][j] == 'O')
			{
				if(vFlag[0][j] == false)
				{
					TraverNeighorhood_Breath( board, vFlag, sFlag, 0, j, row, col);
				}
			}
			
			if(board[row-1][j] == 'O')
			{
				if(vFlag[row-1][j] == false )
				{
					TraverNeighorhood_Breath( board, vFlag, sFlag, row-1, j, row, col);
				}
			}
		}
		
		for(int i=0;i<row;i++)
			for(int j=0;j<col;j++)
				if(sFlag[i][j] == true)
					board[i][j] = 'X';
		
		return;
	}
	
	public void TraverNeighorhood_Breath(char[][] board, boolean[][] vflag, boolean[][] sflag, int cr,int cc, int row, int col)
	{
		java.util.Stack<Integer> toVisNodes = new java.util.Stack<Integer>();
		
		toVisNodes.add(cr*col+cc);
		
		while(!toVisNodes.isEmpty())
		{
			int hashindex = toVisNodes.pop();
			int trow = hashindex / col;
			int tcol = hashindex % col;
			
			if(vflag[trow][tcol] == true)
				continue;
			
			vflag[trow][tcol] = true;
			sflag[trow][tcol] = false;
			
			for(int i=-1;i<=1;i++)
				for(int j=-1;j<=1;j++)
				{
					if( (i==0 || j==0) && (trow+i>=0 && trow+i<row && tcol+j>=0 && tcol+j<col) )
					{
						if( board[trow+i][tcol+j] == 'O' && vflag[trow+i][tcol+j] == false)
						{
							toVisNodes.add((trow+i)*col+tcol+j);
						}
					}
				}
		}
	}
	
	
	public void TraverNeighborhood(char[][] board, boolean[][] vflag, boolean[][] sflag, int cr,int cc, int row, int col)
	{
		//Going to visit board[i][j] which is already marked as unbounded.
		for(int i=-1;i<=1;i++)
			for(int j=-1;j<=1;j++)
			{
				if( (i==0 || j==0) && (cr+i>=0 && cr+i<row && cc+j>=0 && cc+j<col) )
				{
					if( board[cr+i][cc+j] == 'O' && vflag[cr+i][cc+j] == false)
					{
						vflag[cr+i][cc+j] = true;
						sflag[cr+i][cc+j] = false;
						TraverNeighborhood(board, vflag, sflag, cr+i,cc+j, row, col);
					}
				}
			}
	}
	
	public static void main(String[] args) throws Exception
	{
		int row = 0,col = 0;
		//java.util.Scanner scan = new java.util.Scanner(System.in);
		BufferedReader bfread = new BufferedReader(new FileReader("output"));
		String rc = bfread.readLine();
		String[] strs = rc.split(" ");
		row = Integer.parseInt(strs[0]);
		col = Integer.parseInt(strs[1]);
		
		char[][] board = new char[row][col];
		int k = 0;
		while(k<row)
		{
			String str = bfread.readLine();
			for(int j=0;j<col;j++)
				board[k][j]=str.charAt(j);
			k++;
		}
		
		Solution sol = new Solution();
		sol.solve(board);
		
		IOFile ofile = new IOFile();
		ofile.WriteBoard(board, "result");
		System.out.println("Finished");
	}
}