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

spoiler posted @ 2011年4月29日 15:48 in 十个利用矩阵乘法解决的经典题目 , 2713 阅读

题目大意：给你一个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");
    }
}