USACO 2.1.1 The Castle

题目链接： http://train.usaco.org/usacoprob2?a=seBQLs3pEVm&S=castle

思路：复杂的模拟。。。写了我好久。预处理有点毒瘤

/*
ID:zylbeyo1
TASK:castle
LANG:C++
*/
#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
#include <algorithm>
static const int MAXN=600;
static const int MAXM=600;
static const int MAXN1=600;
using namespace std;
struct Wall
{
    bool n,e,s,w;
}wall[MAXN][MAXM];
struct Ans
{
    int num,dir,x,y;
}e[MAXN1];
int m,n,area=1,cnt,Maxx=-1,Max=-1,ans,a[MAXN][MAXM],anss[MAXN1];
bool vis[MAXN][MAXM];
inline int read()
{
    int x=0;bool sign=false;
    char alpha=0;
    while(!isdigit(alpha)) sign|=alpha=='-',alpha=getchar();
    while(isdigit(alpha)) x=(x<<1)+(x<<3)+(alpha^48),alpha=getchar();
    return sign?-x:x;
}
inline int get_max(int a,int b){return a>b?a:b;}
inline void deal_wall(int i,int j)
{
    if(a[i][j]==1) wall[i][j].w=true;
    else if(a[i][j]==2) wall[i][j].n=true;
    else if(a[i][j]==3) wall[i][j].w=true,wall[i][j].n=true;
    else if(a[i][j]==4) wall[i][j].e=true;
    else if(a[i][j]==5) wall[i][j].w=true,wall[i][j].e=true;
    else if(a[i][j]==6) wall[i][j].n=true,wall[i][j].e=true;
    else if(a[i][j]==7) wall[i][j].w=true,wall[i][j].n=true,wall[i][j].e=true;
    else if(a[i][j]==8) wall[i][j].s=true;
    else if(a[i][j]==9) wall[i][j].w=true,wall[i][j].s=true;
    else if(a[i][j]==10) wall[i][j].n=true,wall[i][j].s=true;
    else if(a[i][j]==11) wall[i][j].w=true,wall[i][j].n=true,wall[i][j].s=true;
    else if(a[i][j]==12) wall[i][j].s=true,wall[i][j].e=true;
    else if(a[i][j]==13) wall[i][j].w=true,wall[i][j].s=true,wall[i][j].e=true;
    else if(a[i][j]==14) wall[i][j].s=true,wall[i][j].e=true,wall[i][j].n=true;
    else if(a[i][j]==15) wall[i][j].w=true,wall[i][j].s=true,wall[i][j].e=true,wall[i][j].n=true;
}
namespace p1
{
    static const int dirx[5]={0,-1,0,1,0};
    static const int diry[5]={0,0,1,0,-1};
    inline bool check1(int num,int i,int j)
    {
        if(num==1) return wall[i][j].n?false:true;
        else if(num==2) return wall[i][j].e?false:true;
        else if(num==3) return wall[i][j].s?false:true;
        else return wall[i][j].w?false:true;;
    }
    inline bool check2(int x,int y){return (x<1||y<1||x>n||y>m)?false:true;}
    void dfs(int x,int y,int z)
    {
        a[x][y]=z;
        vis[x][y]=true;
        for(int i=1;i<=4;i++)
        {
            if(check1(i,x,y))
            {
                int dx=x+dirx[i],dy=y+diry[i];
                if(!check2(dx,dy)||vis[dx][dy]) continue;
                area++;
                dfs(dx,dy,z);
            }
        }
    }
    inline void solve1()
    {
        for(int i=1;i<=n;i++)
          for(int j=1;j<=m;j++)
          {
              if(!vis[i][j])
              {
                  ans++;
                  dfs(i,j,ans);
                  Max=get_max(Max,area);
                  anss[ans]=area;
                  area=1;
              }
          }
        printf("%d\n%d\n",ans,Max);
    }
}
namespace p2
{
    inline bool cmp(Ans a,Ans b)
    {
        if(a.num==b.num) return a.y<b.y||(a.y==b.y)&&a.x>b.x||(a.x==b.x&&a.y==b.y)&&a.dir>b.dir;
        return a.num>b.num;
    }
    inline void solve2()
    {
        for(int i=1;i<=n;i++)
          for(int j=1;j<=m;j++)
          {
              if(wall[i][j].n&&i>=2&&a[i-1][j]!=a[i][j])
              {
                  if(anss[a[i-1][j]]+anss[a[i][j]]<Maxx) continue;
                  e[++cnt].num=anss[a[i-1][j]]+anss[a[i][j]];
                  e[cnt].x=i;e[cnt].y=j;
                  e[cnt].dir='N';
                  Maxx=get_max(Maxx,e[cnt].num);
              }
              if(wall[i][j].e&&j+1<=m&&a[i][j+1]!=a[i][j])
              {
                  if(anss[a[i][j+1]]+anss[a[i][j]]<Maxx) continue;
                  e[++cnt].num=anss[a[i][j+1]]+anss[a[i][j]];
                  e[cnt].x=i;e[cnt].y=j;
                  e[cnt].dir='E';
                  Maxx=get_max(Maxx,e[cnt].num);
              }
          }
          sort(e+1,e+cnt+1,cmp);
          printf("%d\n",Maxx);
          printf("%d %d %c\n",e[1].x,e[1].y,e[1].dir);
    }
}
int main()
{
    freopen("castle.in","r",stdin);
    freopen("castle.out","w",stdout);
    m=read();n=read();
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) a[i][j]=read(),deal_wall(i,j);
    memset(a,0,sizeof(a));
    p1::solve1();
    p2::solve2();
    fclose(stdin);
    fclose(stdout);
    return 0;
}