题解 P2199 【最后的迷宫】

· · 题解

洛谷P2199

题目链接

一、题意分析

根据题面我们可以知道

  1. 基本信息：哈利在一个 N\times M 的迷宫中，他需要移动以看到奖杯，赢得比赛。哈利可以向上下左右四个方向行走一格，他移动的非常快，行走一格只需要 1s，也可以向东，东北，东北，西......八个方向看。迷宫的状态有两种：一种是空地，可以行走，在该题中用大写字母 O 来表示；另一种是墙，不可以行走，在该题中用大写字母 X 来表示。哈利不可以透过墙看到奖杯。
  2. 题目需求：题目让我们求出哈利看到奖杯的最短时间。
  3. 输入和输出信息：首先输入 N 和 M，然后输入一个高为 N，宽为 M 的矩阵。题目有多组测试数据，每一组测试数据会给出奖杯的坐标和哈利的坐标，共有四个数，当这四个数均为 0 时，输入结束。对于每一组测试数据，如果哈利可以看到奖杯，那么输出哈利行走的最短时间；如果哈利无法看到奖杯，那么输出 Poor Harry.

二、思路说明

做题要有一个好习惯：先看数据范围。

对于 100\% 的数据 N\times M \le 16384。这很巧妙，因为数据可以是 N = 1,M = 16384，这样用二维数组存储肯定会 MLE，所以要用一维数组存储。二维转一维的方式是求出目前输入的字符是第几个被输入的，可以得出第 i 行第 j 列的字符便是第 (i-1)\times M + j 个输入的。

搞定了存储问题，接下来是处理那些地方可以看到奖杯。

奖杯是不会动，那么每个能看见奖杯的位置也是不变的，可以提前将能看见奖杯的位置找出来，在 v 数组中打上标记，这样可以使不用每走一步就要判断一次能否看到奖杯。

当这些问题全部解决完之后，便是用 bfs 遍历哈利所有可以走的点,第一次走到能看见奖杯的地方便已经得出最优解，这也是为何不适用 dfs 的原因，dfs 在求最短路径时时间复杂度较高，效率远不如 bfs.

三、小坑

多测不清空，报零两行泪。

如果哈利和奖杯的位置一样，那么直接输出 0 即可，不必再进行其它操作。

如果哈利一开始就能看到奖杯，也是直接输出 0 即可，要注意的是这里也是要清空的。

代码