zoj－3497－Mistwald－矩阵

题意：有一个n*m的矩阵，矩阵上每一个格子有四个传送门，分别通向四个格子，题目给出了每个格子的四个传送门所能到达的地方。起点在(1，1)，终点是(n，m)，当走到终点的时候就不能再走了，也就是说一旦你到达了终点，就会直接离开这个矩阵。问说从起点开始走P(0 ≤ P ≤ 100,000,000)步能不能到达终点。

输出的情况是True，Maybe和False。Ture对应的就是走了P步以后只能到达一个点，就是终点。Maybe对应的是走了P步之后还可以到达除了终点以外的其他点。False对应的是P步以后无法到达终点。

做法：

对矩阵做Ｐ次幂，如果可达，那么对应位置应该不为0；

注意：

因为走到（n，m）点之后就不能再走了，所以要把所有的有关于最后一个点的边去掉。

can[i]:第i个点可以一步走到最后一个点。

yes[i]:第i个点可以一步走到非最后一个点

我们可以对矩阵做p-1次幂，然后模拟最后一步。

#include
  
   
#include
   
     #include
    
      #include
     
       using namespace std; #define LL long long #define MOD 1000000007 struct matrix { int mat[31][31]; matrix(){memset(mat,0,sizeof(mat));} }ONE; int n; int can[101]; int yes[101]; matrix mul(matrix A,matrix B) { matrix C; int i,j,k; for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { for(k=1;k<=n;k++) { C.mat[i][j]=C.mat[i][j]|(A.mat[i][k]&B.mat[k][j]); } } } return C; } matrix powmul(matrix A,LL k) { matrix B; for(int i=1;i<=n;i++)B.mat[i][i]=1; while(k) { if(k&1)B=mul(B,A); A=mul(A,A); k>>=1; } return B; } void pan(matrix A) { int leap1=0; int leap2=0; for(int i=1;i
      
       ='0'&&str[k]<='9') { ls++; if(ls%2) { b=str[k]-'0'; if(i==nn&&j==mm)continue; if(a==nn&&b==mm){ can[(i-1)*mm+j]=1; continue; } A.mat[(i-1)*mm+j][(a-1)*mm+b]=1; yes[(i-1)*mm+j]=1; } else a=str[k]-'0'; } } } } matrix B; int Q; LL kk; scanf("%d",&Q); while(Q--) { scanf("%lld",&kk); if(kk==0) { if(nn==1&&mm==1) { cout<<"True"<