矩阵快速幂

zoj 3497 Mistwald
矩阵乘法，但是要先把点从二维变成一维，然后要特殊处理一下终点情况，走到终点就不能再走了。

#include <iostream>  
#include <cstdio>  
#include <cstring>  
using namespace std;  
int mat[30][30], g[30][30], res[30][30];  
int m, n, nm;  
void MatPow(int m1[][30],int m2[][30]){
    int t[30][30];
    for(int i=0;i<nm-1;i++){
        for(int j=0;j<nm;j++){
            t[i][j]=0;
            /*看这里*/
            for(int k=0;k<nm-1;k++){
                if(m1[i][k]&&m2[k][j]){
                    t[i][j]=1;
                    break;
                }
            }
        }
    }
    memcpy(m1,t,sizeof(t));
}

int main(){
    int T;
    int Q,p;
    cin>>T;
    char s[100];
    int X[5],Y[5];
    while(T--){
        cin>>m>>n;
        nm=n*m;
        memset(mat,0,sizeof(mat));
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                scanf("%s",s);
                sscanf(s, "((%d,%d),(%d,%d),(%d,%d),(%d,%d))",  
                       &X[0], &Y[0], &X[1], &Y[1], &X[2], &Y[2], &X[3], &Y[3]);  
                for(int k=0;k<4;k++){
                    X[k]--;
                    Y[k]--;
                    /*看这里*/
                    mat[i*n+j][X[k]*n+Y[k]]=1;
                }
            }
        }
        cin>>Q;
        while(Q--){
            cin>>p;
            if(!p){
                if(nm==1) cout<<"True\\\\n";
                else  cout<<"False\\\\n";
                continue;
            }
            bool ok=true;
            memcpy(g,mat,sizeof(g));
            while(p){
                if(p&1){
                    if(ok){
                        memcpy(res,g,sizeof(g));
                        ok=false;
                    }
                    else 
                        MatPow(res,g);
                }
                p>>=1;
                MatPow(g,g);
            }
            int ans=0;
            for(int i=0;i<nm-1;i++){
                if(res[0][i]){
                    ans++;
                }
            }
            if(res[0][nm-1]){
                if(ans==0)
                    cout<<"True\\\\n";
                else
                    cout<<"Maybe\\\\n";
            }
            else
                cout<<"False\\\\n";
        }
        cout<<endl;
    }
    return 0;
}