记录编号	580825	评测结果	AAAAAAAA
题目名称	城堡	最终得分	100
用户昵称	超人	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2023-07-27 08:28:58	内存使用	0.00 MiB

/*
1: 在西面有墙
2: 在北面有墙
4: 在东面有墙
8: 在南面有墙
*/
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=55;
int visit[maxn][maxn];//floodfill访问标记
int Map[maxn][maxn];
int dwall[5]={1,2,4,8};//0西 1北 2东 3南 对应的墙标记
//Map[x][y] & dwall[k]为 1，2，4，8表示房间(x,y)在西、北、东、南面有墙
int dx[5]={0,-1,0,1};//0西 1北 2东 3南行值改变方案
int dy[5]={-1,0,1,0};//0西 1北 2东 3南列值改变方案
int n,m;
int s[maxn*maxn]={0};
int c_ans=0,max_ans=0;
void init(){
    scanf("%d%d",&m,&n);
    int wall;
    for (int i=1;i<=n;i++)
    for (int j=1;j<=m;j++){
        scanf("%d",&wall);
        Map[i][j]=wall;//读入每个格子墙状态
    }
    memset(visit,-1,sizeof(visit));//floodfill初始化
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++) visit[i][j]=0;
    s[0]=-1;//设置
}
void dfs(int x,int y,int flag){//深搜floodfill
    if (visit[x][y]) return ;//如果访问过(x,y)或越界
    visit[x][y]=flag; s[flag]++;//未访问过标记房间号
    int xx,yy,wall=Map[x][y];//存储新新动态(x,y)及当前房间的墙状态
    for (int k=0;k<4;k++){//0西 1北 2东 3南
        xx=x+dx[k];yy=y+dy[k];
        if (!(wall&dwall[k])) dfs(xx,yy,flag);//如果当前方向无墙
    }
}
void pushwall(){
    int push_ans=max_ans,push_x,push_y;//分别记录推墙后最大面积，坐标、方向
    char push_d;
    for (int j=0;j<=m+1;j++) visit[0][j]=0;//最上一行城外标记为0
    for (int i=0;i<=n+1;i++) visit[i][m+1]=0;//最右一列城外标记为0
    for (int y=1;y<=m;y++)//从西优先扫描
    for (int x=n;x>0;x--){//从南次优先扫描
        int wall=Map[x][y],s1=-1,s2=-1;
        if (visit[x-1][y]^visit[x][y]) {//如果北边有墙
                s1=s[visit[x][y]]+s[visit[x-1][y]];
                if (s1>push_ans) {
                    push_ans=s1;
                    push_x=x;push_y=y; push_d='N';
                }
        }
        if (visit[x][y+1]^visit[x][y]) {//如果东边有墙
                s2=s[visit[x][y]]+s[visit[x][y+1]];
                if (s2>push_ans){
                    push_ans=s2;
                    push_x=x;push_y=y; push_d='E';
                }
        }
    }
    cout<<push_ans<<endl;
    cout<<push_x<<' '<<push_y<<' '<<push_d<<endl;
}
int main(){
    freopen("castle.in","r",stdin);
    freopen("castle.out","w",stdout);
    init();
    for (int i=1;i<=n;i++)
    for (int j=1;j<=m;j++){
       if (visit[i][j]) continue;
       c_ans++;dfs(i,j,c_ans);
       if(s[c_ans]>max_ans) max_ans=s[c_ans];
    }
    cout<<c_ans<<endl<<max_ans<<endl;
    pushwall();
    return 0;
}