记录编号	112140	评测结果	AAAAAAAA
题目名称	城堡	最终得分	100
用户昵称	752199526	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2014-07-15 08:03:02	内存使用	0.38 MiB

#include<iostream>
#include<fstream>
#include<iomanip>
#include<cstdio>
#include<cmath>
#include <cstdlib>
#include<cstring>
#include<cctype>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<cassert>
#include<algorithm>
#include<functional>
#include<ctime>
using namespace std;
ifstream fin("castle.in");
ofstream fout("castle.out");
class Castle
{
public:
	int w,n,s,e;//墙的记号：1为有，0为无，编号代表方向
}vis[55][55]={0,0,0,0};
int M,N,colour[2501],map[55][55],ans=0,maxroom=0,X=1,Y=1;
bool wall_e=false,wall_n=false;
void Flood_Fill_DFS(int x,int y,int newcolour);
void Seek(void);
int main()
{
	//Init
	int newcolour=0;
	memset(map,0,sizeof(map));//所有房间未被访问
	memset(colour,0,sizeof(colour));
	fin>>M>>N;
	for(int i=1;i<=N;i++)
	{
		int k;
		for(int j=1;j<=M;j++)
		{
			fin>>k;//枚举各个数代表的情况
			if(k==0)vis[i][j].n=vis[i][j].e=vis[i][j].s=vis[i][j].w=0;
			else if(k==1)vis[i][j].w=1;
			else if(k==2)vis[i][j].n=1;
			else if(k==4)vis[i][j].e=1;
			else if(k==8)vis[i][j].s=1;
			else if(k==3)vis[i][j].w=vis[i][j].n=1;
			else if(k==5)vis[i][j].w=vis[i][j].e=1;
			else if(k==6)vis[i][j].n=vis[i][j].e=1;
			else if(k==9)vis[i][j].w=vis[i][j].s=1;
			else if(k==10)vis[i][j].n=vis[i][j].s=1;
			else if(k==12)vis[i][j].e=vis[i][j].s=1;
			else if(k==7)vis[i][j].w=vis[i][j].n=vis[i][j].e=1;
			else if(k==11)vis[i][j].w=vis[i][j].n=vis[i][j].s=1;
			else if(k==13)vis[i][j].w=vis[i][j].e=vis[i][j].s=1;
			else if(k==14)vis[i][j].n=vis[i][j].e=vis[i][j].s=1;
			else vis[i][j].n=vis[i][j].e=vis[i][j].s=vis[i][j].w=1;
		}
	}
	//Flood Fill Algortihm 
	for(int i=N;i>=1;i--)
	{
		for(int j=1;j<=M;j++)
		{
			//cout<<map[i][j]<<" ";
			if(map[i][j]==0)//该房间未被访问
			{
				newcolour++;//改变颜色
				//cout<<newcolour<<"　";
				Flood_Fill_DFS(i,j,newcolour);//访问该房间及其连通房间单元
			}
		}
	}
	//Check
	//Step 1:the number of room and the max room
	for(int i=1;i<=newcolour;i++)
		maxroom=max(maxroom,colour[i]);
	fout<<newcolour<<endl<<maxroom<<endl;
	//Step 2:the max room after breaking down the wall
	Seek();
	fout<<ans<<endl;
	fout<<X<<" "<<Y<<" ";
	if(wall_n==true)fout<<"N"<<endl;
	else if(wall_e==true)fout<<"E"<<endl;
	/*for(int k=1;k<=N;k++)
	{
		cout<<endl;
		for(int j=1;j<=M;j++)cout<<map[k][j]<<" ";
	}*/
	return 0;
}
void Flood_Fill_DFS(int x,int y,int newcolour)
{
	if(x<1||x>N||y<1||y>M||map[x][y]!=0)return;
	map[x][y]=newcolour;
	//cout<<map[x][y]<<"S";
	colour[newcolour]++;
	if(vis[x][y].e==0)Flood_Fill_DFS(x,y+1,newcolour);
	if(vis[x][y].w==0)Flood_Fill_DFS(x,y-1,newcolour);
	if(vis[x][y].n==0)Flood_Fill_DFS(x-1,y,newcolour);
	if(vis[x][y].s==0)Flood_Fill_DFS(x+1,y,newcolour);
}
void Seek(void)
{
	for(int y=1;y<=M;y++)
	{
		for(int x=N;x>=1;x--)
		{
			if(vis[x][y].n==1&&map[x-1][y]!=map[x][y])
			{
				int temp=ans; 
				ans=max(ans,colour[map[x-1][y]]+colour[map[x][y]]);
				if(temp<ans){X=x;Y=y;wall_n=true;wall_e=false;}
			}
			if(vis[x][y].e==1&&map[x][y+1]!=map[x][y])
			{
				int temp=ans;
				ans=max(ans,colour[map[x][y+1]]+colour[map[x][y]]);
				if(temp<ans){X=x;Y=y;wall_e=true;wall_n=false;}
			}
		}
	}
}