[USACO][Section 2.1][搜索] The Castle

题目大意：

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

思路：

比较麻烦的搜索题，主要思路是用深搜计算每个房间的面积，时间复杂度属于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<=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