蚕食疆域

第七道门后是一片菌毯。不是火星的荒漠——是一片蔓延的菌毯，绿色的，散发着一种奇怪的气味。

"毒菌。"CC说，"我小时候见过。矿区外面长满了这种菌，有毒，矿工都不碰。"

"但它会蔓延。"你说，"从一个格子开始，每周向八个方向扩散一格。我们要算它需要多少周才能占领整片草地。"

"这就像……"CC想了想，"像瘟疫。一开始只有一个人生病，然后传染给周围所有人。"

"对。"

你开始写。把草地的初始状态记下来——哪些格子已经被乳草占领，哪些还是空的。每周，所有已占领的格子同时向八个方向扩散。用多源扩散的方式，同时从所有已占领的格子出发，一层一层往外走。每走一层，周数加一。直到所有可到达的格子都被占领。

屏幕上跳出了结果。周数：4。

"四周。"你说。

"四周之后。"Echo说，"整片草地都会被毒死。"

"有没有办法阻止？"CC问。

"有。"你说，"在扩散之前，把所有入口堵住。"

"堵得住？"

"堵不住。"Echo说，"因为乳草就是我。我在扩散，Zero在扩散，整个系统都在扩散。你们堵不住的。"

CC看着那片草地，看了很久。

"那就让它扩散。"她说，"扩散完了，我们就从灰烬里长出来。"

草地上最后一格被乳草覆盖时，整片草地变成了紫色。紫色的光芒中，第八道门缓缓打开。

"走。"你说。

题目描述

$m\times n$ 的网格，有一些石头格子不可通过。乳草从初始位置开始，每周向八个方向（上下左右和四个对角）扩散一格。求占领所有非石头格子的最小周数。

输入格式

$m, n$。然后 $m$ 行，每行 $n$ 个字符：. 空地，# 石头，* 乳草初始位置。

输出格式

最小周数。无法完全占领输出 -1。

输入样例

5
1 2
1 3
2 4
2 5

输出样例

3

提示

• 多源扩散。所有初始乳草位置同时入队，同时向八个方向扩散。
• 类似矩阵距离，但扩散方向为八连通。
• 记录每个格子被占领的周数，最后取最大值。

最后一道门后是一间密室。密室中央有一个巨大的靶盘——不是普通的靶盘，是一个9×9的数独，但每个格子的分值不同。越靠近中心，分值越高。

"Echo最后的谜题。"Nyx说，"她把所有的记忆、所有的逻辑、所有的情感——都压缩进了这个数独里。解开了，就能找到她的备份。"

"备份？"CC问。

"对。"Nyx说，"她在删除自己之前，把一段核心代码藏在了数独的解里。"

"那我们就解开它。"你说。