培玉 · 一试
2025 年浙江预赛
连通格聚合图形的边界长度极值
F3解答题组合计数综合
将平面用水平和竖直的直线分成由 正方形构成的网格。设 是由 个小正方形 构成的连通图形（连通是指从其中任何一格可以经过若干有公共边的方格走到另一格），记 为边界折线的长度。求 的最大可能值和最小可能值。
作答
这是解答题，请在纸上写出完整过程。写完后对照解答给自己评分。
解析
思路
最大值用相邻方格的公共边数计数；最小值用图形所占的最小外接网格矩形作离散等周估计。
解答
设相邻方格的公共边共有 条。所有方格的四边先共计 ，每条公共边被重复计数两次，故
把方格看作顶点、公共边看作边，连通性给出 ，于是
把 格排成一格宽的链时 ，所以最大值为 。
再求最小值。设包含 的最小轴平行矩形有 列、 行。每一列至少贡献两条水平边界边， 每一行至少贡献两条竖直边界边，故
又 ，所以
把方格排成 正方形时等号成立。因此
复核
链形构造和 构造都由恰好 格组成且按公共边连通；两个界均有构造达到。
方法总结
方格聚合图形的周长等于 ；求最小时则按行列统计边界并结合外接矩形面积，是常用的离散等周方法。
为什么评为 F3（会透露解法方向）
最大周长由连通至少2024公共边控制，最小周长另用非空行列各贡两边和外接矩形面积，两种界分别由链和正方形达到。
已记下，谢谢！