loj#P2822. 「BalticOI 2014 Day1」警察与强盗

「BalticOI 2014 Day1」警察与强盗

题目描述

本题译自 BalticOI 2014 Day1 T1「Cop and Robber

本题暂时只能支持 C++ / C++ 11 语言提交,需引入 coprobber.h 头文件方可正常评测。

Bytemore 的犯罪率又创历史新高。在所有的违法行为中,抢劫天天发生。然而当每次抢劫发生时,总是只有一个巡警孤身一人在街角的狭窄小巷之间追捕强盗。不幸的是,往往是强盗打赢这场追逐战,因为这些老奸巨猾的强盗早已对这个城市了如指掌。

Bytemore 市公安部门(英文缩写为 BCPD)正在组织一场最高会议来减少犯罪。其中一种可行的解决方案是在追捕盗贼时使用计算机远程协助警察。为此,BCPD 制作了一份精细的城市地图。现在他们需要一个大佬计算机程序来制定追捕策略。

警察追捕强盗的问题可以如下模式化:

  1. 这名警察会选择一个街角巡逻。

  2. 强盗会选择一个街角施行抢劫(他知道警察的位置)。从这时开始,我们总是假设警察与强盗互相知道对方的位置。

  3. 警察所可以进行的移动包括转移到另一个相邻的街角(即从一条小巷转移到另一条与之相连接的小巷)或等待(即不动)。

  4. 强盗所可以进行的移动同样包括转移到另一个相邻的街角。请注意,相比警察,强盗并不能等待,因为逃跑是他们的本能。

  5. 警察与强盗会一直轮流进行动作(从警察开始)直到以下一种情况发生:

  • 强盗能够一直躲避警察,使得强盗能够逃脱;

  • 他们其中任意一个作出移动之后在同一个街角相遇。在这种情况下,警察抓住了强盗。

你需要写一个程序,它对于给定的地图,能够确定警察是否有可能抓到强盗,且若果可以,输出警察抓到强盗时进行的移动数量。

你的程序须假设强盗总是做出最优方案。

你需要写两个函数与交互器进行交互,函数原型分别为:

int start(int N, bool A[MAX_N][MAX_N]);
int nextMove(int R);
  • 其中 start(N, A)传入以下参数:

    • NN——街角的数量(街角以 00N1N - 1 编号);

    • AA——一个二维数组描述小巷:对于所有的 0i,jN10 \le i,\,j \le N-1,若 iijj 不连通,则 A[i,j]=falseA[i,j]=\texttt{false},否则 A[i,j]=trueA[i,j]=\texttt{true}

    所有小巷都是双向的(即对于所有 iijjA[i,j]=A[j,i]A[i,j]=A[j,i]),并且不会出现自环(即对于所有 iiA[i,i]=falseA[i,i]=\texttt{false})。此外,你可以假设警察总能从其他街角通过小巷到达一个街角。

如果警察可能在由参数描述的地图上抓到强盗,函数start应该返回警察与强盗相遇的街角编号。否则返回 1-1

  • nextMove(R) 传入参数 RR,表示当前强盗的所在的街角编号。该函数应返回这次移动之后警察所在的街角编号。

函数 start 必定会在第一次调用函数 nextMove 调用一次。如果 start 返回了 1-1,那么 nextMove 将不会被调用。否则,nextMove 会被反复调用直到追捕行动结束。更确切地说,只要满足以下情况之一,程序必须终止:

  • nextMove 返回了一个不合法的移动;

  • 强盗能够一直躲避警察;

  • 强盗被抓住了。

您可以参考附加文件中的 coprobber.cpp 的格式书写代码。

输入格式

第一行,一个整数 NN,表示街角的个数。

以下 NN 行,包含一个邻接矩阵 AA
其中每行包含 NN 个数字,要么是 00 要么是 11

如果警察可以抓到强盗,下一行为 11,否则为 00

如果上一行为 11,以下将会有 NN 行,描述强盗的策略。
每行 N+1N+1[0,N1][0,N-1] 之间的整数。
rr 行第 cc 列(其中 c<Nc < N)的整数对应的情况下为强盗的回合,警察在街角 rr 而强盗已经移动到街角 cc
主对角线将被忽略。
rr 行的最后一个整数表示如果警察从街角 rr 开始则强盗开始的街角为该数。

数据范围与提示

子任务编号 分数 数据范围 附加条件
1 16 1N5001 \le N \le 500 对于每两个街角,只有一条路线可以互相到达。
2 14 街角与小巷形成的网络为网格形结构。网格至少有两行且街角的编号情况如下图所示。
3 30 2N1002 \le N \le 100
4 40 2N5002 \le N \le 500

你的函数实现须满足下述要求:

  1. 确定警察能否抓到强盗;

  2. 如果警察有可能抓到强盗的话,表示警察可以通过移动抓到强盗。

在子任务 1122 中,你的解决方案应该满足以上要求才能拿到所有分数。
在子任务 3344 中,若你的解决方案只满足要求 11,可以拿到 30%30\% 的子任务分数。如果你的程序只打算拿部分分,则可以通过输出无效的移动来终止程序(例如,使 nextMove 返回 1-1)。