在城市中发生了一起犯罪，犯罪嫌疑人开始逃跑。给出了城市地图。目前，有些警车停留在一些给定的地点，他们试图阻止犯罪嫌疑人。警车和犯罪嫌疑人的车辆拥有相同的最大速度。只有在犯罪嫌疑人比任何一辆警车更早到达某个点时，他才能通过该点。地图上有几个出口，如果犯罪嫌疑人到达任何一个出口，则逃脱成功。找到一种算法来分配警车，使得犯罪嫌疑人无法通过任何路径逃脱。
例如，以下是可能的城市地图。
白色圆圈是嫌疑人的起点，黑色圆圈是警车，小正方形是出口。在这种情况下，可以阻止嫌疑人。一个可能的计划是警车A前往A'，B留在原地，C前往C'。
我的问题可以等价地描述为：
一个化工厂（用白色圆圈标记）发生爆炸，有毒液体以速度
v朝着各个方向流动，救援队伍（用黑色圆圈标记）的最大速度也是v，他们正在试图阻止它。小方块代表他们正在保护的村民。
我的想法
如果我们有 n 辆警车，一种高度低效的方法是列出所有可能的顶点 k 元子集 P，使得：
a) k <= n;
b) 从地图中移除
P中的所有顶点将导致任何出口对嫌疑人不可达；c) 移除
P的任何真子集都将让至少一个出口对嫌疑人可达。
然后，我们可以轻松确定是否每个 P 中的顶点都可以在嫌疑人之前由警察覆盖。
但是，我该如何列出所有可能的 P 呢？
@Lior Kogan:
请看这张地图：
如果这是一场双方都知道对方策略的翻转游戏，警察会获胜，因为他可以守卫嫌疑人去的那一边。
但在我的问题中，警察输了，因为他永远不知道嫌疑人可能选择哪一边。
