CF2068G A Very Long Hike

你计划在葡萄牙北部的 Peneda-Gerês 国家公园进行远足。该公园以两座最高峰命名：Peneda（1340 米）和 Gerês（1545 米）。 在本问题中，公园被建模为一个无限平面，其中每个整数坐标位置 $(x, y)$ 都有特定海拔。海拔由 $n \times n$ 的矩阵 $h$ 周期性重复构成。具体来说，对于任意整数 $a, b$ 且 $0 \leq x, y < n$，位置 $(x + an, y + bn)$ 的海拔为 $h[x][y]$。 当处于位置 $(x, y)$ 时，你可以移动到四个相邻位置之一：$(x, y+1)$、$(x+1, y)$、$(x, y-1)$ 或 $(x-1, y)$。移动所需时间为 $1 + \lvert \text{alt}_1 - \text{alt}_2 \rvert$，其中 $\text{alt}_1$ 和 $\text{alt}_2$ 分别为当前位置和目的地的海拔。 初始位置为 $(0, 0)$。计算在 $10^{20}$ 秒内可以到达的不同位置数量。只要相对误差小于 $10^{-6}$，答案即视为正确。

第一行包含整数 $n$（$2 \le n \le 20$）——描述海拔的矩阵尺寸。 接下来 $n$ 行每行包含 $n$ 个整数。第 $(i+1)$ 行的第 $(j+1)$ 个数为 $h[i][j]$（$0 \le h[i][j] \le 1545$）——表示位置 $(i, j)$ 的海拔。

输出在 $10^{20}$ 秒内可到达的不同位置数量。只要相对误差小于 $10^{-6}$，答案即视为正确。

第一个样例中，Peneda-Gerês 国家公园所有位置的海拔均为 $3$。因此相邻位置间移动时间恒为 $1$ 秒。 此时可以证明，位置 $(x, y)$ 在 $10^{20}$ 秒内可达当且仅当 $|x|+|y| \le 10^{20}$。可计算出可达位置总数为 $20\,000\,000\,000\,000\,000\,000\,200\,000\,000\,000\,000\,000\,001$，该数值可用 $2 \cdot 10^{40}$ 近似表示且相对误差小于 $10^{-6}$。样例输出中 $2 \cdot 10^{40}$ 为正确答案，但精确数值亦可作为答案。 第二个样例中，所有满足 $x-1$ 和 $y-1$ 能被 $3$ 整除的位置 $(x, y)$ 海拔为 $1545$，其余位置海拔为 $0$。例如，$(4, 10)$ 到 $(4, 9)$ 的移动时间为 $1546$ 秒，而 $(3, 2)$ 到 $(4, 2)$ 的移动时间为 $1$ 秒。 在 $2$ 秒内可达的位置包括所有满足 $|x|+|y| \le 2$ 的位置（除位于山顶的 $(1, 1)$）。可计算出在 $10^{20}$ 秒内共有 $19\,999\,999\,999\,999\,999\,931\,533\,333\,333\,333\,333\,863\,441$ 个可达位置，该数值可用 $2 \cdot 10^{40}$ 近似表示且相对误差小于 $10^{-6}$。样例输出中 $2 \cdot 10^{40}$ 为正确答案，但精确数值亦可作为答案。 翻译由 DeepSeek R1 完成