题意：给定一个有向图（最多25个节点，每个节点的出度最多为4），给定起点和终点，然后从起点开始走，走到终点就停止，否则一直往下走，问能不能P步到达终点。也就是说从起点出发，走一条长度为P的路径，路径中间点不能经过终点（但可以反复经过其他点）。如果从起点出发P步后，不能到达终点，就是False，如果可以到达终点也可以到其他别的点，就是Maybe，如果P步后只能到达终点（到别的点没有长度为P的路径），则是Yes。
题目看了看天没看懂
解决方法非独立思考
借鉴以下博客
http://blog.csdn.net/sdjzujxc/article/details/8720573
不过题解还是要自己写
想象以下矩阵相乘的方程
c.mat[i][j]=(c.mat[i][j]+a.mat[i][k]*b.mat[k][j])；
假设 a b相等
是否可以看做 i到j的路径数目=i到k的路径数目*k到j的路径数目？
所以走p次的各个点到各个点的方案数 就是
保存在了A^p这个矩阵中，利用矩阵快速幂求出
若A[0][m*n-1]>0 说明一定可以到终点
若A[0][0]~A[0][m*n-2]>0且A[0][m*n-1]>0 代表可能到终点
A[0][m*n-1]=0 不能到终点
不过要注意 m*n-1只能走一次 即终点只能走一次 所以m*n-1 不能作为矩阵乘法中的k出现
代码如下：
/*
注意不能计算 A[i][m*n-1]*B[m*n-1][j]；
*/
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#define LL long long
#define oo 0x13131313
using namespace std;
LL M,N,k,m;
void init()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
}
struct node
{
LL mat[30][30];
void clear() {memset(mat,0,sizeof(mat));}
void ret() {
clear();
for(int i=0;i<30;i++)
mat[i][i]=1;
}
};
node A;
void input()
{
int x1,y1,x2,y2,x3,y3,x4,y4;
A.clear();
scanf("%d%d
",&M,&N);
for(int i=0;i<M;i++)
for(int j=0;j<N;j++)
{
scanf("((%d,%d),(%d,%d),(%d,%d),(%d,%d)) ",&x1,&y1,&x2,&y2,&x3,&y3,&x4,&y4);
x1--,y1--,x2--,y2--,x3--,y3--,x4--,y4--;
A.mat[i*N+j][x1*N+y1]=1;
A.mat[i*N+j][x2*N+y2]=1;
A.mat[i*N+j][x3*N+y3]=1;
A.mat[i*N+j][x4*N+y4]=1;
}
}
node matmult(node a,node b,LL mod)
{
node c;c.clear();
for(int i=0;i<(N*M);i++)
for(int j=0;j<(N*M);j++)
for(int k=0;k<(N*M-1);k++)
c.mat[i][j]=(c.mat[i][j]+a.mat[i][k]*b.mat[k][j])%mod;
return c;
}
node quickmatpow(node a,LL n,LL mod)
{
node c;c.ret();
while(n!=0)
{
if(n&1==1) c=matmult(c,a,mod);
n=n>>1;
a=matmult(a,a,mod);
}
return c;
}
void solve()
{
int ok,ok1;
node c;
int Q,P;
cin>>Q;
while(Q--)
{
ok=0;ok1=0;
cin>>P;
c=quickmatpow(A,P,21323);
for(int i=0;i<M*N-2;i++)
if(c.mat[0][i]>0) ok=1;
if(c.mat[0][M*N-1]>0) ok1=1;
if(ok&&ok1) printf("Maybe
");
else if(ok1) printf("True
");
else if(!ok1) printf("False
");
}
printf("
");
}
int main()
{
//init();
int T;
cin>>T;
while(T--)
{
input();
solve();
}
return 0;
}