首页 > 代码库 > zoj3497Mistwald矩阵

zoj3497Mistwald矩阵

  判断i到j    是否k步可达。

#include <cstdio>#include <algorithm>#include <iostream>#include <string.h>typedef long long LL;using namespace std;int n;int x[100], y[100];struct Matrix{    int m[40][40];};Matrix Mul(Matrix a, Matrix b){    Matrix ans;    for (int i = 0; i < n; i++){        for (int j = 0; j < n; j++){            ans.m[i][j] = 0;            for (int k = 0; k < n; k++){                ans.m[i][j] |= a.m[i][k] * b.m[k][j];            }        }    }    return ans;}Matrix quick(Matrix a, int b){    Matrix  ans;    for (int i = 0; i < n;i++)    for (int j = 0; j < n; j++)        ans.m[i][j] = (i == j);    while (b){        if (b & 1) ans = Mul(ans, a);        a = Mul(a, a);        b >>= 1;    }    return ans;}Matrix init(){    int a, b;    Matrix ans;    cin >> a >> b;    n = a*b;    for (int i = 0; i < n;i++)    for (int j = 0; j < n; j++)        ans.m[i][j] = 0;    for (int i = 0; i < a; i++){        for (int j = 0; j < b; j++){            getchar();            scanf("((%d,%d),(%d,%d),(%d,%d),(%d,%d))", &x[0], &y[0], &x[1], &y[1], &x[2], &y[2], &x[3], &y[3]);            if(i==a-1&&j==b-1)continue;//图中路径不能经过终点            int t = i*b + j;            for (int k = 0; k < 4; k++){                x[k]--; y[k]--;                int t1 = x[k] * b + y[k];                ans.m[t][t1] = 1;            }        }    }    return ans;}void gao(Matrix a, int b){    int flag = 0;    int flag1 = 0;    Matrix ans;    ans = quick(a, b);    if(!ans.m[0][n-1]){        printf("False\n"); return ;    }    for(int i = 1;i<n-1;i++)    if(ans.m[0][i]){        printf("Maybe\n");return ;    }    printf("True\n");}int main(){    int T; int q; int t;    cin >> T;    while (T--){        Matrix ans = init();        cin >> q;        while(q--){            scanf("%d", &t);            gao(ans, t);        }        cout<<endl;    }    return 0;}

 

zoj3497Mistwald矩阵