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

#include <cstdio>
#include <cstdlib>
#include <cstring> 
#include <queue>
#include <algorithm>
#include <utility>
#define NOR 1
#define SOU 2
#define WES 3
#define EAS 4
#define MAXN 55
#define NUL 0
#define mp(i,j) make_pair(i,j)
using namespace std;
int Wall[MAXN][MAXN][5];
int M,N;
int Top=0,Ans;
int Num[MAXN][MAXN];
int Len[MAXN*MAXN]={0};
int step[5][2]={{},{-1,0},{1,0},{0,-1},{0,1}};
typedef pair<int,int> Pair;
queue<Pair> Q;

inline int lowbit(int x){return x&(-x);}
void init()
{
	memset(Wall,NUL,sizeof(Wall));
	scanf("%d %d\n",&M,&N);
	int x,y;
	for(int i=1;i<=N;i++)
	{
		for(int j=1;j<=M;j++)
		{
			scanf("%d\n",&x);
			while(x)
			{
				y=lowbit(x);
				if(y==8) Wall[i][j][SOU]=1;
				if(y==4) Wall[i][j][EAS]=1;
				if(y==2) Wall[i][j][NOR]=1;
				if(y==1) Wall[i][j][WES]=1;
				x-=y;
			}/*
			printf("%d %d -> NORTH: %d    ",i,j,Wall[i][j][NOR]);
			printf("SOUTH: %d    ",Wall[i][j][SOU]);
			printf("WEST: %d     ",Wall[i][j][WES]);
			printf("EAST: %d\n",Wall[i][j][EAS]);*/
		}
	}
}



inline void BFS(int x,int y)
{
	int res=0;
	Q.push(mp(x,y));
	Num[x][y]=Top;
	int tx,ty,nx,ny;
	while(!Q.empty())
	{
		res++;
		tx=Q.front().first,ty=Q.front().second;
		Q.pop();
		for(int i=1;i<=4;i++)
		{
			nx=tx+step[i][0];
			ny=ty+step[i][1];
			if(nx>N || nx<1 || ny<1 || ny>M) continue;
			if(Num[nx][ny]) continue;
			if(Wall[tx][ty][i]) continue;
			Num[nx][ny]=Top;
			Q.push(mp(nx,ny));
		}
	}
	Len[Top]=res;
}

inline void solve()
{
	memset(Num,NUL,sizeof(Num));
	for(int i=1;i<=N;i++)
		for(int j=1;j<=M;j++)
		{
			if(Num[i][j]!=0) continue;
			Top++;
			BFS(i,j);
		}
	printf("%d\n",Top);	
	printf("%d\n",*max_element(Len,Len+Top+1));
	
	int MaxTmp=0;
	int Posx,Posy;char dir;
	int ti,tj;
	int tb1,tb2,tmp;
	for(int j=1;j<=M;j++)
	{
		for(int i=N;i>=1;i--)
		{
			tb1=Num[i][j];
			if(i>1) //North
			{
				ti=i-1,tj=j,tb2=Num[ti][tj];
				if(tb1!=tb2)
				{
					tmp=Len[tb1]+Len[tb2];
					if(tmp>MaxTmp)
					{
						MaxTmp=tmp;
						Posx=i,Posy=j,dir='N';
					}
				}
			}
			
			if(j<M) //East
			{
				ti=i,tj=j+1,tb2=Num[ti][tj];
				if(tb1!=tb2)
				{
					tmp=Len[tb1]+Len[tb2];
					if(tmp>MaxTmp)
					{
						MaxTmp=tmp;
						Posx=i,Posy=j,dir='E';
					}
				}
			}
			
		}
	}
	printf("%d\n%d %d %c",MaxTmp,Posx,Posy,dir);
	return;
}

int main()
{
	freopen("castle.in","r",stdin);
	freopen("castle.out","w",stdout);
	init();
	solve();
	return 0;
}