题目大意：
给出一个地图，要求计算有多少个房间、最大房间的面积、删除哪一面墙会使合并房间的面积最大。
思路：
比较麻烦的搜索题，主要思路是用深搜计算每个房间的面积，时间复杂度属于O(n)级别。
代码：
/*
ID: lujunda1
LANG: C++
PROG: castle
*/
#include
#include
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=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>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>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;jsize[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=1;i--)
//注意题目中要求的搜索优先级，靠西最优先靠南其次。
for(int dir=0;dir>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();
}