P3507. 相同数字组成图形的周长

题目背景

本题属于 岛屿的周长 的 加强版，从计算 1 种连通区域 变成了计算 多种连通区域。

注意事项

特别注意：题目并没有说同一种元素只会存在 一块连通块，不能够根据示例 先入为主。

解法一：直接遍历二维矩阵

思路展开 参考代码没有做 DFS/BFS 搜索，而是用「逐格数暴露边」的方式直接统计周长。第一步按输入落子：网格固定为 64 × 64、初始全 0，每行输入的第一个数是该图形的填充值 val，后面的数字两两一组是坐标 (x, y)，把 grid[x][y] 置为 val；同时用列表 nums 按输入顺序记录出现过的值，保证最后按输入顺序输出结果。第二步遍历整个 64 × 64 网格：对每个格子取它的值 val，检查上、下、左、右四个方向——如果邻格出界，或者邻格的值与 val 不同，这条边就暴露在图形外沿，给哈希表 ansMap 中 val 对应的周长加 1；两个同值格子相邻的公共边则两边都不计，相当于内部边被抵消。这样每条外沿边恰好被它所属的格子统计一次，某个值的累计结果就是该数字所有格子构成图形的周长。这种按值累计的写法也天然覆盖了前文提醒的坑：同一个数字即使散成多个不相连的图形，各块的周长也会自动累加到同一个数字名下。最后按 nums 的顺序从 ansMap 取值、用空格拼接输出。

复杂度分析 网格大小固定为 64 × 64。设 n 为输入行数（图形个数），T 为输入的坐标对总数。

• 时间：落子阶段为 O(T)；主计算阶段对 64 × 64 个格子各检查 4 个方向，共 64 × 64 × 4 次常数操作，是一个固定上界；输出阶段为 O(n)。总时间复杂度为 O(T + 64 × 64)，其中网格部分是常量级固定开销。
• 空间：grid 固定占 64 × 64 的整型数组；ansMap 与 nums 的大小和出现的数字种类数同量级。空间复杂度为 O(64 × 64 + n)。