Mistwald zoj 3497

佚名 6年前 (2019-04-11) 随笔 1943人围观抢沙发百度已收录

链接

[https://vjudge.net/contest/294259#problem/K]

题意

就是有个m*n矩阵
出发(1,1) 出口（m,n）
然后给出每个点能到大的四个位置
而且一旦到达终点就得出去不能往回走
然后给出多次询问，p表示是否恰好刚好p步走到终点，如果还可能到其他点就是maybe
否则就是true ,如果不能到达就false

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

分析

就是离散数学里的那个可达矩阵，这里由于数据较小。就总共m*n个点就行了
然后再加上矩阵快速幂即可
还有就是关于getchar这个输入时要注意。我tm气死了，被这个读入给搞了

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int t,N,M,p,q,s;
struct Matrix{
    int m[50][50];
}I,ans,A;
Matrix Mul(Matrix a,Matrix b)
{
    int i, j, k;
    Matrix c;
    for(i = 1; i <= s; i++)
    {
        for(j = 1; j <= s; j++)
        {
            c.m[i][j]=0;
            for(k = 1; k <= s; k++)
            {
                c.m[i][j]+=(a.m[i][k]*b.m[k][j]);
            }
        }
    }
    return c;
}
 
Matrix quickpagow(int n)
{
    Matrix m = A, b = I;
    while(n)
    {
        if(n & 1)
            b = Mul(b,m);
        n = n >> 1;
        m = Mul(m,m);
    }
    return b;
}
int main(){
    //ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>t;
    while(t--){
        memset(I.m,0,sizeof(I.m));
        memset(ans.m,0,sizeof(ans.m));
        memset(A.m,0,sizeof(A.m));
        cin>>M>>N;
        getchar();
        s=M*N;
        for(int i=1;i<=s;i++)
        I.m[i][i]=1;
        int x1,y1,x2,y2,x3,y3,x4,y4;
        for(int i=1;i<=M;i++){
            for(int j=1;j<=N;j++){
           scanf("((%d,%d),(%d,%d),(%d,%d),(%d,%d))",&x1,&y1,&x2,&y2,&x3,&y3,&x4,&y4);
           getchar();
            if(i==M&&N==j) continue;
            A.m[(i-1)*N+j][(x1-1)*N+y1]=1;
            A.m[(i-1)*N+j][(x2-1)*N+y2]=1;
            A.m[(i-1)*N+j][(x3-1)*N+y3]=1;
            A.m[(i-1)*N+j][(x4-1)*N+y4]=1;
           }
        }
        cin>>q;
        while(q--){
            cin>>p;
            ans=quickpagow(p);
            if(ans.m[1][s]==0)
            cout<<"False\n";
            else{
                bool flag=0;
                for(int i=1;i<=s-1;i++)
                if(ans.m[1][i]){
                    flag=1; break;
                }
                if(flag) cout<<"Maybe\n";
                else cout<<"True\n";
            }
        }
        cout<<"\n";
    }
    return 0;
}