SP12562 CDC12_G - Glory War

Ronny 因为没有通过守卫考试（守卫反对作弊，而且非常愤怒，因为有人帮助他作弊），他将家人留在了一栋建筑中，并躲在那里。此时，彩虹国的人正在狂暴地攻击地球的居民，大街上到处都是尸体和惊慌失措的人群。Ronny 必须保护他的家人，因此他决定快速消灭建筑内的所有彩虹国人。 Ronny 对彩虹国的人了解不多，但他知道在行动时需要保持安静。因此，他选择把吵闹的枪收起来，无法远距离攻击敌人。为了解决彩虹国人，他可以使用一把刀或者一个漂亮的飞踢。Ronny 需要站到敌人所在的位置上才能将其消灭。建筑物内满是瓦砾，有些路径甚至会通向陷阱。不过，Ronny 可以利用绳子在楼层之间上下移动。当然，如果目的地是全是瓦砾的地方，他无法使用绳子。 给定建筑的尺寸（包括宽度、高度和楼层数）以及敌人的位置，你需要设计一个程序来帮助 Ronny 以最小步数消灭所有彩虹国人，从而尽量减少行动噪音。 请注意： - Ronny 的起点是建筑一楼（第一个楼层）西北角的位置 (1,1,1)。 - Ronny 只能向东、西、南、北四个方向移动，此外，他还可以在移动过程中爬上或下到不同楼层。 - Ronny 在任何时候都不能离开建筑，且建筑物没有地下室，所以他不能低于第一层。

第一行输入一个整数 $T$，表示测试用例的数量。接下来的每个测试用例包含两个整数 $N$ 和 $H$，其中 $N$ 表示每层楼的宽度和纵深，$H$ 表示楼层的数量。随后会有 $H$ 个 $N \times N$ 的矩阵，每个矩阵描述每一层楼的布局。楼层布局由以下字符构成： - 字符 `#` 表示瓦砾。 - 字符 `.` 表示空闲区域。 - 字符 `*` 表示彩虹国人。

对于每个测试用例，输出格式要求是「Scenario #i:」，其中 $i$ 是测试用例的编号（从 1 开始），后接 Ronny 消灭所有彩虹国人所需的最小步数。如果无法完成，输出 -1。

- $1 \le T \le 10$ - $1 \le N \le 50$ - $1 \le H \le 10$ **本翻译由 AI 自动生成**