卢俊达

题目大意：

给出一个地图，要求计算有多少个房间、最大房间的面积、删除哪一面墙会使合并房间的面积最大。

思路：

比较麻烦的搜索题，主要思路是用深搜计算每个房间的面积，时间复杂度属于O(n)级别。

代码：

/*
ID: lujunda1
LANG: C++
PROG: castle
*/
#include<iostream>
#include<stdio.h>
using namespace std;
int n,m,map[51][51],size[51][51],num[51][51];
//map[][]用于存储围墙信息。
//size[i][j]的含义为(i,j)所处房间的大小。
//num[i][j]的含义为(i,j)所处房间的编号。 
bool mark[51][51];
//深搜时对访问过的位置进行标记。 
bool range(int i,int j)
//判断(i,j)是否超界。 
{
	if(i>=1&&i<=n&&j>=1&&j<=m)
		return true;
	return false;
}
int dfs(int i,int j)
//深搜，用于计算房间面积。 
{
	if(!range(i,j)||mark[i][j])
	//判断是否超界或已访问过。 
		return 0;
	mark[i][j]=true;
	int sum=0;
	for(int dir=0;dir<4;dir++)
		if((map[i][j]>>dir)%2==0)
		//把每个位置上的围墙数据表示成一个4位二进制，可以发现每一位都对应一个方向的墙。 
			sum+=dfs(i+(dir-2)%2,j+(dir-1)%2);
			//(i+(dir-2)%2,j+(dir-1)%2)表示与(i,j)一墙之隔的位置的坐标。 
	return sum+1;
}
void updata(int i,int j,int val,int order)
//由于深搜只能将完整面积返回到房间中第一个被访问的位置上，所以需要通过更新操作更新所有位置的size信息。
//val表示(i,j)所处房间的大小。
//order表示(i,j)所处房间的编号。 
{
	if(!range(i,j)||size[i][j])
		return;
	size[i][j]=val;
	num[i][j]=order;
	for(int dir=0;dir<4;dir++)
		if((map[i][j]>>dir)%2==0)
			updata(i+(dir-2)%2,j+(dir-1)%2,val,order);
}
void get_size()
//通过updata()和dfs()对size[][]进行赋值。 
{
	int total=0,max=0;
	//total用于记录方案总数。
	//max用于记录房间面积最大值。 
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(!mark[i][j])
			{
				updata(i,j,dfs(i,j),++total);
				max=max>size[i][j]?max:size[i][j];
			}
	printf("%d\n%d\n",total,max);
}
void remove_wall()
//找到题目所要求的墙，并记录新合并的房间的面积。 
{
	int max=0,wall_y,wall_x;
	//合并房间面积的最大值。
	//wall_y、wall_x表示墙所在位置的纵横坐标。 
	char wall,wall_order[4]={'W','N','E','S'};
	//wall存储墙的方向字符。
	//关于墙的方向的搜索优先级对应的字符。 
	for(int j=1;j<=m;j++)
		for(int i=n;i>=1;i--)
		//注意题目中要求的搜索优先级，靠西最优先靠南其次。 
			for(int dir=0;dir<4;dir++)
				if((map[i][j]>>dir)%2)
				//若此方向有墙 
				{
					int y=i+(dir-2)%2,x=j+(dir-1)%2;
					if(range(y,x)&&num[i][j]!=num[y][x])
					//判断是否超界，两个相邻位置的房间编号是否不同。 
					{
						int temp=size[i][j]+size[y][x];
						//temp表示两房间的面积和。 
						if(max<temp)
						//若max<temp，则更新max和记录该墙的相关信息。 
						{
							max=temp;
							wall_y=i;
							wall_x=j;
							wall=wall_order[dir];
						}
					}
				}
	printf("%d\n%d %d %c\n",max,wall_y,wall_x,wall);
}
int main()
{
	freopen("castle.in","r",stdin);
	freopen("castle.out","w",stdout);
	scanf("%d%d",&m,&n);
	//先输入列，再输入行。 
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			scanf("%d",&map[i][j]);
			mark[i][j]=false;
			size[i][j]=0;
		}
	get_size();
	remove_wall();
}