P3511. 地图寻宝

解题思路

计算数位和

本题的重点在于理解数位和的概念。 所谓数位和，指的是一个正整数的各个位的和。比如 11 的数位和是 1 + 1 = 2。

对于任意一个正整数 n，其数位和可以通过以下两种方式任选其一进行计算。在效率上，数学方法略优于字符串方法，但因为数据量不大，所以都可以使用。

数学方法

字符串方法

构建数位和矩阵

在拿到地图的大小 n * m 之后，就可以通过双重循环遍历的方式，构建出每一个位置的数位和矩阵 grid。

从起点开始进行搜索

拿到数位和矩阵 grid 之后，由于小华从起点出发上下左右均可以移动，所以问题就转化为了从起点 `(0, 0)` 开始进行图的遍历能够到达多大面积的地图。类似 经典题型、岛屿的最大面积。

这个问题用 DFS 或 BFS 都可以完成，直接套模板即可。

代码

解法一：DFS

复杂度分析 设地图为 m 行 n 列，坐标的十进制位数为 d（坐标最大不超过几万量级，d 很小，可视作常数）。

• 时间：预构建数位和矩阵需要对每个格子计算一次横、纵坐标的数位和，单次计算是 O(d) 的取模循环，整体 O(m·n·d)，近似 O(m·n)。DFS 阶段由 checklist 保证每个格子最多被进入一次，每次检查 4 个方向，累计 O(m·n)。总时间复杂度为 O(m·n)。
• 空间：数位和矩阵 grid 与 checklist 各占 O(m·n)；DFS 递归栈在最坏情况（可达区域连成一条长链）下深度可达 O(m·n)。

注意本题只需从 (0, 0) 出发做一次搜索、统计可达格子数即可，不必像「岛屿的最大面积」那样枚举所有起点，所以代码里 dfs 只在 main 中被调用一次，主要开销反而在预构建数位和矩阵上。