如何通过警察和强盗问题构建图表？

Question

这是我考虑过的两部分问题。

问题陈述：

在一个m×n的矩形场中，有一个强盗R和两个警察C1和C2。每一个三个从某个初始正方形开始，在追逐的开始，R，C1，C2全部知道彼此的位置。

R首先移动，然后是C1和C2。它们只能向上，向下，向左或向右移动。一些由于存在障碍，因此无法访问正方形。如果C1或C2达到平方R亮，然后他们抓住R。

为了逃脱，R必须在网格的周长上达到正方形X。如果R在被C1或C2捕获之前到达平方X，则R成功逃脱。否则，R无法逃脱。

作为输入，我们提供：m（行数）和n（列数）的值，R，C1，C2的初始坐标以及不可访问的正方形的列表。

I）使用提供的输入，如何使用邻接表来构造图以解决问题。分析图形创建的运行时。

由于网格表示，我实际上是在考虑使用邻接矩阵，但是我们要求使用和邻接列表。结果，我对应该视为该问题的顶点和边缘感到困惑。我认为网格中的每个正方形都将是一个顶点，并且其边缘将是其所有相邻正方形，至少是它可以到达的正方形，最大为4个正方形。那么我的邻接表是否应该按n对存储所有m个，然后为每对保持邻居的链接列表，即可达的正方形？如果我沿这条路线走，将有（m * n）个顶点，然后对于每个顶点，我必须检查哪些正方形可以到达（上，下，左，右）以及该正方形是否不可访问，所以我会必须扫描作为输入提供的无法访问的列表，这将花费O（n）时间。因此，我猜这将使我花O（m * n）来创建图。我可以做得更好吗？

[II]给定您在（I）部分中创建的图，描述了一种检查R是否可以逃逸的算法。

*假设：R，C1和C2可以忽略的策略。 R，C1，C2以“智能”方式移动还是完全随机移动都没关系。

由于R在追逐开始之前就声明了它的目的地，我认为这仅是R是否从其起点到目的地方块的路径的问题。那么我可以运行DFS并检查R是否可以到达目的地吗？但是，我不知道R能够避免C1和C2。

感谢指导。

Answer 1

像您这样的声音几乎都知道如何构建图形，但是最好给每个顶点一个数字而不是保持（m，n）个元组。

1. 分配N * M个列表的数组。网格上的每个位置（x，y）将对应于该阵列中的插槽x + n * y。该插槽将包含相邻可访问数字的列表；如果有障碍，则为null。
2. 现在，用每个位置的空列表初始化数组
3. 对于每个障碍物，将其对应的阵列插槽设置为空。
4. 对于网格位置（x，y），如果其顶点为(array[x+n*y]!=null)，则检查其邻居以填写其邻接表。例如，如果array[x+1+n*y]!=null，则[x+n*y]的列表将包括[x+1+n*y]。

结果表示形式非常紧凑，可以用于许多目的。由于顶点的度数<= 4，所以邻接表比邻接矩阵要有效得多。

程序的其余部分也将大大简化，因为它不必处理坐标或对原始网格一无所知。

不幸的是，“ * Assumption”将所有乐趣带出了第二部分。