loj#P2822. 「BalticOI 2014 Day1」警察与强盗
「BalticOI 2014 Day1」警察与强盗
题目描述
本题译自 BalticOI 2014 Day1 T1「Cop and Robber」
本题暂时只能支持 C++ / C++ 11 语言提交,需引入 coprobber.h
头文件方可正常评测。
Bytemore 的犯罪率又创历史新高。在所有的违法行为中,抢劫天天发生。然而当每次抢劫发生时,总是只有一个巡警孤身一人在街角的狭窄小巷之间追捕强盗。不幸的是,往往是强盗打赢这场追逐战,因为这些老奸巨猾的强盗早已对这个城市了如指掌。
Bytemore 市公安部门(英文缩写为 BCPD)正在组织一场最高会议来减少犯罪。其中一种可行的解决方案是在追捕盗贼时使用计算机远程协助警察。为此,BCPD 制作了一份精细的城市地图。现在他们需要一个大佬计算机程序来制定追捕策略。
警察追捕强盗的问题可以如下模式化:
-
这名警察会选择一个街角巡逻。
-
强盗会选择一个街角施行抢劫(他知道警察的位置)。从这时开始,我们总是假设警察与强盗互相知道对方的位置。
-
警察所可以进行的移动包括转移到另一个相邻的街角(即从一条小巷转移到另一条与之相连接的小巷)或等待(即不动)。
-
强盗所可以进行的移动同样包括转移到另一个相邻的街角。请注意,相比警察,强盗并不能等待,因为逃跑是他们的本能。
-
警察与强盗会一直轮流进行动作(从警察开始)直到以下一种情况发生:
-
强盗能够一直躲避警察,使得强盗能够逃脱;
-
他们其中任意一个作出移动之后在同一个街角相遇。在这种情况下,警察抓住了强盗。
你需要写一个程序,它对于给定的地图,能够确定警察是否有可能抓到强盗,且若果可以,输出警察抓到强盗时进行的移动数量。
你的程序须假设强盗总是做出最优方案。
你需要写两个函数与交互器进行交互,函数原型分别为:
int start(int N, bool A[MAX_N][MAX_N]);
int nextMove(int R);
-
其中
start(N, A)
传入以下参数:-
——街角的数量(街角以 到 编号);
-
——一个二维数组描述小巷:对于所有的 ,若 与 不连通,则 ,否则
所有小巷都是双向的(即对于所有 和 ,),并且不会出现自环(即对于所有 ,)。此外,你可以假设警察总能从其他街角通过小巷到达一个街角。
-
如果警察可能在由参数描述的地图上抓到强盗,函数start
应该返回警察与强盗相遇的街角编号。否则返回 。
- 而
nextMove(R)
传入参数 ,表示当前强盗的所在的街角编号。该函数应返回这次移动之后警察所在的街角编号。
函数 start
必定会在第一次调用函数 nextMove
调用一次。如果 start
返回了 ,那么 nextMove
将不会被调用。否则,nextMove
会被反复调用直到追捕行动结束。更确切地说,只要满足以下情况之一,程序必须终止:
-
nextMove
返回了一个不合法的移动; -
强盗能够一直躲避警察;
-
强盗被抓住了。
您可以参考附加文件中的 coprobber.cpp
的格式书写代码。
输入格式
第一行,一个整数 ,表示街角的个数。
以下 行,包含一个邻接矩阵 。
其中每行包含 个数字,要么是 要么是 。
如果警察可以抓到强盗,下一行为 ,否则为 。
如果上一行为 ,以下将会有 行,描述强盗的策略。
每行 个 之间的整数。
第 行第 列(其中 )的整数对应的情况下为强盗的回合,警察在街角 而强盗已经移动到街角 。
主对角线将被忽略。
第 行的最后一个整数表示如果警察从街角 开始则强盗开始的街角为该数。
数据范围与提示
子任务编号 | 分数 | 数据范围 | 附加条件 |
---|---|---|---|
1 | 16 | 对于每两个街角,只有一条路线可以互相到达。 | |
2 | 14 | 街角与小巷形成的网络为网格形结构。网格至少有两行且街角的编号情况如下图所示。 | |
3 | 30 | 无 | |
4 | 40 |
你的函数实现须满足下述要求:
-
确定警察能否抓到强盗;
-
如果警察有可能抓到强盗的话,表示警察可以通过移动抓到强盗。
在子任务 与 中,你的解决方案应该满足以上要求才能拿到所有分数。
在子任务 与 中,若你的解决方案只满足要求 ,可以拿到 的子任务分数。如果你的程序只打算拿部分分,则可以通过输出无效的移动来终止程序(例如,使 nextMove
返回 )。