题目描述

算法1

Flood fill $O(n)$

思路

题目一共四个问

第一行：城堡的房间数目。

第二行：最大的房间的大小

第三行：移除一面墙能得到的最大的房间的大小

第四行：移除哪面墙可以得到面积最大的新房间

前两问是Flood Fill，后两问是枚举

分析

从题意出发

2 1
15 15

要破除掉的墙壁是两个方块中间的那堵墙

5 5
3 2 6 3 6
1 8 4 1 4
13 7 13 9 4
3 0 2 6 5
9 8 8 12 13

要破除掉的墙壁是第一行第一列方块的上方，那堵墙

题面表明

“选择最佳的墙来推倒。有多解时选最靠西的，仍然有多解时选最靠南的。同一格子北边的墙比东边的墙更优先。”

因此，推倒的时候，要打一下擂台。

框架

一、BFS求得连通块个数，最大连通块的面积

求连通块的时候，记录一下当前块属于哪个连通块，并把所有的连通块的面积记录下来。为了后面推导墙壁的时候，两个连通块面积相加

二、从上至下，从右至左的遍历。为了有西面的选西面的，有南面的选南面的。

判断一个方格的北面或者东面是否是墙，诸多合法判断后，把他推导，获得两个连通块的面积和，来更新擂台上记录的最大值

C++ 代码

#include <iostream>
#include <algorithm>
#include <fstream>

#define x first
#define y second

using namespace std;

const int N = 55, M = N * N;

typedef pair<int, int> PII;

int g[N][N];
bool st[N][N];
PII q[M];

int n, m;

int dx[4] = {0, -1, 0, 1}, dy[4] = {-1, 0, 1, 0};

int idx, f[M];  //连通块编号，连通块的面积
int g_of_idx[N][N]; //记录每个方格属于哪个连通块
int max_area; //记录最大面积
int max_i = -1, max_j = -1;
char max_dir;
string dir = "WNES";

int bfs(int sx, int sy)
{   
    int area = 0;
    int hh = 0, tt = 0;   //模板hh = 0, tt = -1; 此处默认有一个start结点，tt = 0
    q[0].x = sx, q[0].y = sy;
    st[sx][sy] = true;

    idx++;       //每一个新队列，产生一个新的连通块

    while (hh <= tt)
    {
        area++;
        PII t = q[hh++];

        g_of_idx[t.x][t.y] = idx;   //标记这个方块属于哪个房间

        for (int i = 0; i < 4; i++)
        {
            int a = t.x + dx[i], b = t.y + dy[i];

            //越界，被遍历过，continue
            if (a < 0 || a >= n || b < 0 || b >= m) continue;
            if (st[a][b]) continue;

            //这个方格是墙，就continue
            if (g[t.x][t.y] >> i & 1) continue;

            //入队
            ++tt;
            q[tt].x = a, q[tt].y = b;
            st[a][b] = true;
        }
    }

    f[idx] = area; //记录这个编号连通块的面积，记录在f[]里面

    return  area;
}   

int main()
{
    //freopen("P1457_4.in", "r", stdin);

    scanf("%d%d", &m, &n);

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            scanf("%d", &g[i][j]);

    int area = 0, cnt = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
        {
            if (!st[i][j])
            {
                area = max(area, bfs(i, j));
                cnt++;
            }
        }

    printf("%d\n%d\n", cnt, area);

    for (int i = 0; i < n; i++)
        for (int j = m - 1; j >= 0; j--)
            for (int k = 1; k <= 2; k++)  //遍历每个方格的北面和东面，是否是墙，可以推倒
            {
                if ((g[i][j] >> k & 1) != 1) continue; //当前的方格不是墙，就要continue

                int tx = i + dx[k], ty = j + dy[k];
                if (tx < 0 || tx >= n || ty < 0 || ty >= m) continue;

                if (g_of_idx[i][j] == g_of_idx[tx][ty]) continue;

                int sum_area = f[g_of_idx[i][j]] + f[g_of_idx[tx][ty]];
                if (sum_area > max_area)
                {
                    max_area = sum_area;
                    max_i = i;
                    max_j = j;
                    max_dir = dir[k];
                }
                else if (sum_area == max_area)
                {
                    //有多解时选最靠西的，仍然有多解时选最靠南的。同一格子北边的墙比东边的墙更优先。
                    if ((j == max_j && i > max_i) || (i == max_i && j < max_j))
                    {
                        max_area = sum_area;
                        max_i = i;
                        max_j = j;
                        max_dir = dir[k];
                    }

                }
            }

    printf("%d\n", max_area);
    printf("%d %d %c\n", max_i+1, max_j+1, max_dir);  //下标起始问题

    return 0;
}