记录编号	51591	评测结果	AAAAAAAA
题目名称	城堡	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2012-12-27 16:35:49	内存使用	0.34 MiB

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstdlib>
#include<algorithm>
using namespace std;
class point{
	public:
	bool e,w,s,n;//四方是否有墙
	int a;//第几个房间
};
point board[55][55];
int space[2555]={0},sum=1;//每间房的大小,房间数
int remax=-1,rex,rey;//移除一面墙后的最大房间大小,墙相邻房间的坐标
char redir;//方向
int m,n;
void input(void){
	int i,j,temp;
	scanf("%d%d",&n,&m);//我承认我把m和n搞反了......本程序为m行n列
	for(i=0;i<m;i++){
		for(j=0;j<n;j++){
			board[i][j].a=0;
			scanf("%d",&temp);
			board[i][j].w=(temp%2==0)?0:1,temp/=2;
			board[i][j].n=(temp%2==0)?0:1,temp/=2;
			board[i][j].e=(temp%2==0)?0:1,temp/=2;
			board[i][j].s=(temp%2==0)?0:1,temp/=2;
		}
	}
}
void floodfill(int x,int y,int p){//从(x,y)开始,标记为p
	queue<pair<int,int> > s;
	s.push(make_pair(x,y)),board[x][y].a=p;
	int x1,y1;
	while(!s.empty()){
		x1=s.front().first,y1=s.front().second,space[p]++,s.pop();
		if(board[x1][y1].e==0&&board[x1][y1+1].a==0) s.push(make_pair(x1,y1+1)),board[x1][y1+1].a=p;//东
		if(board[x1][y1].w==0&&board[x1][y1-1].a==0) s.push(make_pair(x1,y1-1)),board[x1][y1-1].a=p;//西
		if(board[x1][y1].n==0&&board[x1-1][y1].a==0) s.push(make_pair(x1-1,y1)),board[x1-1][y1].a=p;//北
		if(board[x1][y1].s==0&&board[x1+1][y1].a==0) s.push(make_pair(x1+1,y1)),board[x1+1][y1].a=p;//南
	}
}
void floodfill(void){//好吧我承认我想不起来这函数应该叫啥了......
	int p=1,i,j;
	for(i=0;i<m;i++){
		for(j=0;j<n;j++){
			if(board[i][j].a==0) floodfill(i,j,p++);
		}
	}
	sum=p-1;
}
int largestroom(void){
	int i,max=-1;
	for(i=1;i<=sum;i++) if(space[i]>max) max=space[i];
	return max;
}
void remove(void){
	int i,j,temp1,temp2;
	for(j=0;j<n;j++){//从西到东,从南到北.....这奇葩的审美
		for(i=m-1;i>=0;i--){
			if(board[i][j].n&&board[i-1][j].a!=board[i][j].a){//单位北方
				temp1=board[i-1][j].a,temp2=board[i][j].a;
				if(space[temp1]+space[temp2]>remax) remax=space[temp1]+space[temp2],rex=i,rey=j,redir='N';
			}
			if(board[i][j].e&&board[i][j+1].a!=board[i][j].a){//单位东方
				temp1=board[i][j+1].a,temp2=board[i][j].a;
				if(space[temp1]+space[temp2]>remax) remax=space[temp1]+space[temp2],rex=i,rey=j,redir='E';
			}
		}
	}
}
int main(){
	freopen("castle.in","r",stdin);
	freopen("castle.out","w",stdout);
	input();
	floodfill();
	remove();
	printf("%d\n%d\n",sum,largestroom());
	printf("%d\n%d %d %c\n",remax,rex+1,rey+1,redir);
	return 0;
}