SP11496 RPLJ - Just the distance

Deisy 正在进行一个机器人项目。在将机器人送往一家重要公司之前，她希望先在安全的环境中进行测试。为此，她为机器人设计了一张完整的地图。目前，机器人的测试版还有些笨拙，它只能往北、南、东或西四个方向移动，而不能沿对角线移动。Deisy 有些担心这种限制是否会影响机器人的最佳路径选择，她想知道如果允许对角线走法，是否总会优于目前的四个方向移动。 你需要帮助 Deisy 比较机器人的对角移动步数与实际四向移动步数的优劣。具体而言，你需要判断从地图 A 到地图 B 或从地图 B 到地图 A，机器人可以从任意一个点开始，并抵达另一张地图中的最近点。在选择起点时，Deisy 可以随意选择任意属于某个地图的点作为起点，而不必比较属于同一个地图点集的情况。 “地图”的定义是由一组星号（*）组成，它们通过上、下、左、右四个方向相连，如果两个星号通过这四个方向相连，即它们互为邻接。

输入的第一行包含一个整数 $T$，表示有 $T$ 组测试用例。对于每个测试用例，首先是一个整数 $N$，接着是 $N$ 行，每行包含 $N$ 个字符，表示机器人的地图。空闲区域用 '-' 表示，被星号占据的区域用 '*' 表示。可以保证每次输入总会有两个地图。

对于每个测试用例，输出 “Scenario #i: ”，其中 $i$ 是当前的测试用例编号，后面接上一个数字。如果机器人可以通过正常的四个方向找到最短路径，则输出 1；如果对角线的步行距离总是短于或等于正常步数，则输出 0。 **数据范围** - $2 \le N \le 1000$ **样例数据** **输入** ``` 2 5 --**-- --**-- ------ **---- **---- 4 *--* *--* *--* *--* ``` **输出** ``` Scenario #1: 0 Scenario #2: 1 ``` **说明** 对于第一个测试用例，无论从地图 A 还是 B 的任何一点开始，在每种情况下，对角线移动总是能找到更短的路径，所以输出结果应为 0。 注意：如果 Deisy 发现对角线步数和正常步数一样，她会选择四向移动的方式。在这种情况下，输出结果应该是 1。 **本翻译由 AI 自动生成**