题目描述

本题译自 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)传入以下参数：

  • $N$——街角的数量（街角以 $0$ 到 $N - 1$ 编号）；

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

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

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

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

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

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

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

• 强盗被抓住了。

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

输入格式

第一行，一个整数 $N$，表示街角的个数。

以下 $N$ 行，包含一个邻接矩阵 $A$。
其中每行包含 $N$ 个数字，要么是 $0$ 要么是 $1$。

如果警察可以抓到强盗，下一行为 $1$，否则为 $0$。

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

数据范围与提示

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

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

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

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

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