这题看上去很复杂，但实际上没有那么困难。

1. 因为这个图中有很多连通块，认为是房间：需要对同一个房间的 cell 做上标记，并且计算连通块的大小： 对每个未染色的单元 dfs 搜索染色就可以了。 这是基本操作。
2. 抽象化 “墙” 这个概念， 便于操作。有两种墙，
   1. 一种是虚拟的抽象的概念：南北西东4个墙的标记和方向；
   2. 另一种是实墙，可以评估其价值：拆除后可以变成的最大房间大小。

这题主要坑在最后一个地方： 对于一个实墙，如果拆除价值同样大，则选择 $y$ 大的或 $x$ 小的； 如果是同一个 cell（即 $x$ 和 $y$ 相同），则优先选择 N 墙，即北墙。

可以直接用结构体比较选择最大。注意写好比较函数就可以了。

还写了打印 castle 的函数，很好玩。

#include <cstdio>

const int MAX_N = 52;
int n, m;
int walls[MAX_N][MAX_N];
int mark[MAX_N][MAX_N] = {0}; // 染色

struct Wall
{
    int dx, dy;  // direction
    int c, mask; // char and bit mask
    Wall(int dx, int dy, int c, int mask): dx(dx), dy(dy), c(c), mask(mask) {}
    bool exist(int v) { return mask & v; }
};

struct RealWall
{
    int x, y;
    int c, value;
    RealWall() {}
    RealWall(int x, int y, int c, int value): x(x), y(y), c(c), value(value) {}
};

bool cmp(RealWall &a, RealWall &b)
{
    if (a.value != b.value)
        return a.value > b.value;
    if (a.y != b.y)
        return a.y < b.y;   // farthest to the west
    if (a.x != b.x)
        return a.x > b.x;   // farthest to the south
    // same module
    return a.c == 'N';   // a.c must be 'N' or 'E'
}

Wall wall[4] = 
{
    Wall(0, -1, 'W', 1 << 0),
    Wall(-1, 0, 'N', 1 << 1),
    Wall(0, 1, 'E', 1 << 2),
    Wall(1, 0, 'S', 1 << 3),
};

bool WALL_W(int x) { return wall[0].exist(x); }
bool WALL_N(int x) { return wall[1].exist(x); }
bool WALL_E(int x) { return wall[2].exist(x); }   // for Wall E
bool WALL_S(int x) { return wall[3].exist(x); }

void print_castle()
{
    int i, j;
    for (i = 1; i <= m; ++i)
    {
        // print walls
        for (j = 1; j <= n; ++j)
        {
            if (WALL_N(walls[i][j])) printf("####");
            else printf("#   ");
        }
        printf("#\n");
        // print through
        for (j = 1; j <= n; ++j)
        {
            if (WALL_W(walls[i][j])) printf("#   ");
            else printf("    ");
        }
        printf("#\n");
    }
    for (j = 1; j <= n; ++j) printf("####");
    printf("#\n");
}

int dfs(int x, int y, int color)
{
    if (mark[x][y]) return 0;
    mark[x][y] = color;

    int count = 1;

    for (int i = 0; i < 4; ++i)
        if (!wall[i].exist(walls[x][y]))
            count += dfs(x + wall[i].dx, y + wall[i].dy, color);

    return count;
}

int main()
{
    int i, j;
    scanf("%d %d", &n, &m);

    for (i = 1; i <= m; ++i)
        for (j = 1; j <= n; ++j)
            scanf("%d", &walls[i][j]);
    // print_castle();

    int color = 1;
    int size[MAX_N * MAX_N] = {0};

    for (i = 1; i <= m; ++i)
        for (j = 1; j <= n; ++j)
            if (!mark[i][j])
            {
                size[color] = dfs(i, j, color);
                ++color;
            }

    int max_size = 0;
    for (i = 1; i < color; ++i)
        if (max_size < size[i]) max_size = size[i];
        // printf("%d: %d\n", i, size[i]);

    // select max
    int c, nc;
    RealWall bestwall = RealWall(0, 0, 0, 0), current;
    for (i = m; i > 0; --i)
        for (j = 1; j <= n; ++j)
        {
            c = mark[i][j];
            for (int k = 0; k < 4; ++k)
            {
                nc = mark[i + wall[k].dx][j + wall[k].dy];
                if (wall[k].exist(walls[i][j]) && c != nc)
                {
                    current = RealWall(i, j, wall[k].c, size[c] + size[nc]);
                    if (cmp(current, bestwall))
                        bestwall = current;
                }
            }
        }

    printf("%d\n", color - 1);
    printf("%d\n", max_size);
    printf("%d\n", bestwall.value);
    printf("%d %d %c\n", bestwall.x, bestwall.y, bestwall.c);

    return 0;
}