The Castle

题目描述

一座城堡被分成 $m\times n$ 个方块（ $m\leqslant 50$ ， $n\leqslant 50$ ），每个方块用整数 $P$ （ $0\leqslant P\leqslant 15$ ）描述墙： $1$ 西墙、 $2$ 北墙、 $4$ 东墙、 $8$ 南墙， $P$ 是这些数字之和，室内一堵墙会被相邻两格各描述一次；共享一条边且公共边无墙的方块属于同一个房间，建筑中至少有两个房间。输入第一行是 $m$ （南北方向长度），第二行是 $n$ （东西方向长度），后面 $m$ 行每行 $n$ 个整数表示每个方块的 $P$ ；输出两行：房间总数，以及最大房间的面积（方块数）。样例输入：

text

1
2
3
4
5
64
7
11 6 11  6  3 10  6
7  9  6 13  5 15  5
1 10 12  7 13  7  5
13 11 10 8 10 12 13

输出样例：5、9（5 个房间，最大面积 9）。

思路

把每个方块看成顶点，相邻且公共边无墙时连边，房间就是连通分量、面积就是分量大小；依次扫描每个方块，遇到未访问的就做一次洪水填充标记整个分量并统计大小，同时更新房间数与最大面积，总复杂度 $O(mn)$ 。判断能否走向某方向只需检查当前格自己那一侧的墙位即可——室内的墙被相邻两格各定义一次，只查一侧不会漏判。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 01:46
# update_at: 2026-09-30 01:46

import sys

# 四个方向的 (行增量, 列增量, 该方向的墙位)：北墙 2 挡住往上，南墙 8 挡住往下，
# 西墙 1 挡住往左，东墙 4 挡住往右。位值是题面给定的，不能改顺序含义。
DIRS: tuple[tuple[int, int, int], ...] = ((-1, 0, 2), (1, 0, 8), (0, -1, 1), (0, 1, 4))


def room_sizes(m: int, n: int, wall: list[list[int]]) -> list[int]:
    """返回每个房间的面积（方块数）：对每个未访问格做一次洪水填充。

    格子编号 id = r * n + c，邻居能否过去只看当前格自己那一侧的墙位——
    因为室内的墙被相邻两格各定义一次，只查一侧就足够了，不必两侧都查。
    """
    seen = bytearray(m * n)
    sizes: list[int] = []
    for start in range(m * n):
        if seen[start]:
            continue
        seen[start] = 1                       # 入栈即标记，每个格子只被展开一次
        stack = [start]
        size = 0
        while stack:
            size += 1
            r, c = divmod(stack.pop(), n)
            for dr, dc, bit in DIRS:
                nr, nc = r + dr, c + dc
                in_range = 0 <= nr < m and 0 <= nc < n   # 先判界，避免读到别的行
                can_step = in_range and not wall[r][c] & bit and not seen[nr * n + nc]
                if can_step:
                    seen[nr * n + nc] = 1
                    stack.append(nr * n + nc)
        sizes.append(size)
    return sizes


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    m, n = next(data), next(data)             # 行数（南北）在前，列数（东西）在后
    wall = [[next(data) for _ in range(n)] for _ in range(m)]

    sizes = room_sizes(m, n, wall)
    print(f"{len(sizes)}\n{max(sizes)}")       # 题面保证至少两个房间，max 不会空


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 07:02
 * update_at: 2026-10-05 07:03
 */
#include <cstdio>

typedef long long ll;

const int MAXN = 55;

int m, n;                       // m 行（南北方向），n 列（东西方向）
int wall[MAXN][MAXN];           // wall[r][c]：该方块的墙位和，1西 2北 4东 8南
bool vis[MAXN][MAXN];           // 洪水填充的访问标记

// 四个方向：行增量、列增量、当前格这一侧对应的墙位
const int DR[4] = {-1, 1, 0, 0};
const int DC[4] = {0, 0, -1, 1};
const int BIT[4] = {2, 8, 1, 4};

// 从 (sr, sc) 出发洪水填充，返回这个房间（连通分量）的面积
// 室内的墙被相邻两格各定义一次，只查当前格自己那一侧的墙位即可
int dfs(int sr, int sc) {
    if (sr < 0 || sr >= m || sc < 0 || sc >= n) return 0; // 越界保护
    if (vis[sr][sc]) return 0;
    vis[sr][sc] = true;
    int size = 1;
    for (int d = 0; d < 4; ++d) {
        if (wall[sr][sc] & BIT[d]) continue; // 这一侧有墙，过不去
        size += dfs(sr + DR[d], sc + DC[d]);
    }
    return size;
}

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

    int room_count = 0; // 房间总数
    int best = 0;       // 最大房间面积
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
            if (!vis[i][j]) {
                ++room_count;
                int size = dfs(i, j);
                if (size > best) best = size;
            }

    printf("%d\n%d\n", room_count, best);
    return 0;
}

目录

题目描述

思路

参考代码