ZOJ (3497 Mistwald 关于矩阵求点直接连通的问题)

题目大意：给你一个N*M 的矩阵， 矩阵里的每个点代表一个全送阵， 代表当前点可以全送到4个点，你的出发点是（1，1）；要到达的点是（n,m），这里要注意的是，一旦任何点到了（n,m）点之后 就会被全送出去，离开整个地图，所以这里算是一个陷阱，您要把（n,m）点能够到达的点，全部置0，（”0“代表他不能到达某个点）

题目分析：

这里是Maxtrix67 大牛总结的 第八个矩阵的经典应用:

给定一个有向图，问从A点恰好走k步（允许重复经过边）到达B点的方案数mod p的值
把 给定的图转为邻接矩阵，即A(i,j)=1当且仅当存在一条边i->j。令C=A*A，那么C(i,j)=ΣA(i,k)*A(k,j)，实际上就 等于从点i到点j恰好经过2条边的路径数（枚举k为中转点）。类似地，C*A的第i行第j列就表示从i到j经过3条边的路径数。同理，如果要求经过k步的 路径数，我们只需要二分求出A^k即可;

题目让我们求的是他们是否连通，这里只需用1与0带入即可，

我们这里在乘的过程不是求和，而是用到“与”操作，因为我们要得出的结果不是路径数，而是 是否能经过K步到达该点～

代码+部分注释：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
struct M {
	int s[30][30];
};
struct M unit;
int n;
struct M multiply(struct M a,struct M b){
	struct M c;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++){
			c.s[i][j]=0;
			for(int k=1;k<=n;k++)
                               //：注意下面这个操作，是“|”而不是“+”这里是求是否能到达
                               //而不是求 到达的路径数目！
				c.s[i][j]=(c.s[i][j]|a.s[i][k]*b.s[k][j]);
		}
	return c;
}
struct M paw(struct M a,int t){
	struct M ans=unit;
	struct M b=a;
	while(t){
		if(t%2==1)
			ans=multiply(ans,b);
		b=multiply(b,b);
		t/=2;
	}
	return ans;
}
int main(){
	struct M a;
	memset(unit.s,0,sizeof(unit.s));
	char str[100];
	int num[10];
	for(int i=1;i<=30;i++)
		unit.s[i][i]=1;
	int h,z,p,cas,t;
	int s,e,i,j,k;
	scanf("%d",&cas);
	while(cas--){
		memset(a.s,0,sizeof(a.s));
		scanf("%d %d",&h,&z);
		n=h*z;
		for(i=1;i<=h;i++)
			for(j=1;j<=z;j++){
				scanf("%s",str);
				sscanf(str,"((%d,%d),(%d,%d),(%d,%d),(%d,%d))",&num[1],&num[2],&num[3],&num[4],&num[5],&num[6],&num[7],&num[8]);
				s=(i-1)*z+j;
				for(k=1;k<=8;k+=2){
					e=(num[k]-1)*z+num[k+1];
					a.s[s][e]=1;
				}
			}
                //：转换成邻接矩阵后，a.s[n][]就是
              //代表原来地图里的[n][m]点与其他点的链接状态
              //因为题意说，凡是到了[n][m]点之后，就会马上
           //全送出去，离开这个地图，所以我们要把[n][m]到其他点的
           //状态值都赋为0！
		for(i=1;i<=n;i++)
			a.s[n][i]=0;
		scanf("%d",&p);
		while(p--){
			scanf("%d",&t);
			struct M  c=paw(a,t);
			if(c.s[1][n]==0)
				printf("False\n");
			else{   
				int x;
				for(x=1;x<=n;x++){
					if(c.s[1][x]==1)
						break;
				}
					if(n==x)
						printf("True\n");
					else
						printf("Maybe\n");
			}
		}
		printf("\n");
	}
}