Mistwald zoj 3497

链接

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

题意

就是有个m*n矩阵

出发(1,1) 出口（m,n）

然后给出每个点能到大的四个位置

而且一旦到达终点就得出去不能往回走

然后给出多次询问，p表示是否恰好刚好p步走到终点，如果还可能到其他点就是maybe

否则就是true ,如果不能到达就false

分析

就是离散数学里的那个可达矩阵，这里由于数据较小。就总共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;

}

巴特西

Mistwald zoj 3497

链接

题意

分析

代码

最新文章

热门文章