题意：给定一个有向图（最多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\n",&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\n");

    else if(ok1) printf("True\n");

    else if(!ok1) printf("False\n");

   }

   printf("\n");

}

int main()

{

   //init();

   int T;

   cin>>T;

	while(T--)

    {

        input();

        solve();

    }

    return 0;

}