castle.cpp

USACO chapter two.Useful for beginners.

/*
ID: chenkai4
PROG: castle
LANG: C++
*/
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("castle.in");
ofstream out("castle.out");

int M,N;

int ttcount=0,largest=0;
int belong[52][52]={0};
bool cantgo[52][52][4]={0};

int area[2501]={0};

int tlargest = 0;
int wallx=52,wally=0;char wallD;

#define MAX(A,B) (A>B?A:B)

void floodfill(int x,int y)
{
	belong[y][x]=ttcount;
	area[ttcount]++;
	if(x<M)
	if(!cantgo[y][x][2]&&(belong[y][x+1]==0))
		floodfill(x+1,y);
	if(x>1)
	if(!cantgo[y][x][0]&&(belong[y][x-1]==0))
		floodfill(x-1,y);
	if(y<N)
	if(!cantgo[y][x][3]&&(belong[y+1][x]==0))
		floodfill(x,y+1);
	if(y>1)
	if(!cantgo[y][x][1]&&(belong[y-1][x]==0))
		floodfill(x,y-1);
}

void floodfill()
{
	for(int a=1;a<=N;a++)
		for(int b=1;b<=M;b++)
			if(belong[a][b]==0)
			{
				ttcount++;
				floodfill(b,a);
				largest = MAX(largest,area[ttcount]);
			}
}

int main()
{
	in>>M>>N;int t;
	for(int a=1;a<=N;a++)
		for(int b=1;b<=M;b++)
		{
			in>>t;
			if(t&1==1)
				cantgo[a][b][0]=true;
			if(((t>>1)&1)==1)
				cantgo[a][b][1]=true;
			if(((t>>2)&1)==1)
				cantgo[a][b][2]=true;
			if(((t>>3)&1)==1)
				cantgo[a][b][3]=true;
		}
	floodfill();
	for(int a=1;a<=N;a++)
		for(int b=1;b<=M;b++)
		{
			if(b<M)
			if(cantgo[a][b][2])
			{
				if(belong[a][b]!=belong[a][b+1])
				if((area[belong[a][b]]+area[belong[a][b+1]]>tlargest)
					||( (area[belong[a][b]]+area[belong[a][b+1]]==tlargest) && (b<=wallx && a>=wally)))
				{
					wallx=b;
					wally=a;
					tlargest = area[belong[a][b]]+area[belong[a][b+1]];
					wallD='E';
				}
			}
			if(a>1)
			if(cantgo[a][b][1])
			{
				if(belong[a][b]!=belong[a-1][b])
				if((area[belong[a][b]]+area[belong[a-1][b]]>tlargest)
					||( (area[belong[a][b]]+area[belong[a-1][b]]==tlargest) && (b<=wallx && a>=wally)))
				{
					wallx=b;
					wally=a;
					tlargest = area[belong[a][b]]+area[belong[a-1][b]];
					wallD='N';
				}
			}
		}
	out<<ttcount<<endl<<largest<<endl<<tlargest<<endl<<wally<<" "<<wallx<<" "<<wallD<<endl;
	return 0;
}