gistfile1.cpp

#include <fstream>
using namespace std;
char maze[201][77];
int  dist[2][201][77];


class outdoor
{
public:
	int i,j;
};
int W,H;
void flood(int i,int j,int level,int k);
int main()
{
	ifstream fin("maze1.in");
	ofstream fout("maze1.out");
	
	fin>>W>>H;
	char ignorec = fin.get();//otherwise it will be a quotation "
	
	outdoor od[2];
	int k = 0 ;
	for ( int i = 0 ; i<2*H+1 ;i++)
	{
		int j = 0;
		for ( ; j<2*W+1 ;j++)
		{
			maze[i][j] = fin.get();
			if (((i==0||i==2*H)&&maze[i][j]==' ')||((j==0||j==2*W)&&maze[i][j]==' '))
			{
				od[k].i = i;
				od[k++].j = j;
			}

		}
		char ignore_n = fin.get();
		maze[i][j] = '\0';
	}
	//flood fill
	for (int k = 0 ; k<2 ;k++)
	{
		if (od[k].i==0)
			od[k].i++;
		if (od[k].j==2*W)
			od[k].j--;
		if (od[k].j==0)
			od[k].j++;
		if (od[k].i==2*H)
			od[k].i--;
	}
	int maxsofar;
	for (int k=0;k<2;k++)
	{

		flood(od[k].i,od[k].j,1,k);	
		
		

	}
	//search the max
	for (int i=0;i<2*H;i++)
	{
		for (int j =0;j<2*W;j++)
		{
			int temp = min(dist[0][i][j],dist[1][i][j]);
			if (temp>maxsofar)
			{
				maxsofar=temp;
			}
		}
	}
	fout<<maxsofar<<endl;

	fin.close();
	fout.close();
	return 0;
}


void flood(int i,int j,int level,int k)
{
	if (dist[k][i][j]==0)
	{
		dist[k][i][j] = level;
	}
	else if (level>=dist[k][i][j])
	{
		return;
	}
	else if (level<dist[k][i][j])
	{
		dist[k][i][j] = level;
	}



	//north
	if (i>1&&maze[i-1][j]==' ')
	{
		flood(i-2,j,level+1,k);
	}
	//east
	if (j<2*W-1&&maze[i][j+1]==' ')
	{
		flood(i,j+2,level+1,k);
	}
	//south
	if (i<2*H-1&&maze[i+1][j]==' ')
	{
		flood(i+2,j,level+1,k);
	}
	//west
	if (j>1&&maze[i][j-1]==' ')
	{
		flood(i,j-2,level+1,k);
	}


}