题目
In chapter 4 of the game Trails in the Sky SC, Estelle Bright and her friends are crossing Mistwald to meet their final enemy, Lucciola.
Mistwald is a mysterious place. It consists of M * N scenes, named Scene (1, 1) to Scene (M, N). Estelle Bright and her friends are initially at Scene (1, 1), the entering scene. They should leave Mistwald from Scene (M, N), the exiting scene. Note that once they reach the exiting scene, they leave Mistwald and cannot come back. A scene in Mistwald has four exits, north, west, south, and east ones. These exits are controlled by Lucciola. They may not lead to adjacent scenes. However, an exit can and must lead to one scene in Mistwald.
Estelle Bright and her friends walk very fast. It only takes them 1 second to cross an exit, leaving a scene and entering a new scene. Other time such as staying and resting can be ignored. It is obvious that the quicker they leave Mistwald, the better.
Now you are competing with your roommate for who uses less time to leave Mistwald. Your roommate says that he only uses P seconds. It is known that he lies from time to time. Thus, you may want to code and find out whether it is a lie.
Input
There are multiple test cases. The first line of input is an integer T ≈ 10 indicating the number of test cases.
Each test case begins with a line of two integers M and N (1 ≤ M, N ≤ 5), separated by a single space, indicating the size of Mistwald. In the next M lines, the ith line contains N pieces of scene information, separated by spaces, describing Scene (i, 1) to Scene (i, N). A scene description has the form "((x1,y1),(x2,y2),(x3,y3),(x4,y4))" (1 ≤ xk ≤ M; 1 ≤ yk ≤ N; 1 ≤ k ≤ 4) indicating the locations of new scenes the four exits lead to. The following line contains an integer Q (1 ≤ Q ≤ 100). In the next Q lines, each line contains an integer P (0 ≤ P ≤ 100,000,000), which is the time your roommate tells you.
Test cases are separated by a blank line.
Output
For each P, output one of the following strings in one line: "True" if it cannot be a lie; "Maybe" if it can be a lie; "False" if it must be a lie.
Print a blank line after each case.
Sample Input
2
3 2
((3,1),(3,2),(1,2),(2,1)) ((3,1),(3,1),(3,1),(3,1))
((2,1),(2,1),(2,1),(2,2)) ((3,2),(3,2),(3,2),(3,2))
((3,1),(3,1),(3,1),(3,1)) ((3,2),(3,2),(3,2),(1,1))
3
1
2
10
2 1
((2,1),(2,1),(2,1),(2,1))
((2,1),(2,1),(2,1),(2,1))
2
1
2
Sample Output
Maybe
False
Maybe
True
False
这个题很久以前组队赛的时候做过，那时候太菜了，不会做
这个题就是把坐标换成邻接矩阵中的一个点，然后对邻接矩阵做一下快速幂运算，然后得到一个数组；这个数组就是走p次后的地图；然后判断p次后是否能正好到达（m,n）点。
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<iostream>
using namespace std;
struct mat
{
int m[30][30];
}ans;
int x[4],y[4];
int n,m,si;
mat operator * (mat a, mat b)
{
mat ret;
int x;
for(int i=0;i<si;i++)
{
for(int j=0;j<si;j++)
{
x = 0;
for(int k=0;k<si;k++)
{
x += (a.m[i][k] * b.m[k][j]);
ret.m[i][j] = x;
}
}
}
return ret;
}
mat pow_mat(mat a, int x)
{
mat ret;
memset(ret.m,0,sizeof(ret.m));
for(int i=0;i<si;i++) ret.m[i][i] = 1;
while(x)
{
if(x & 1) ret = ret*a;
a = a*a;
x >>= 1;
}
return ret;
}
void print(mat tmp)
{
printf("***************\n");
for(int i=0;i<si;i++)
{
for(int j=0;j<si;j++)
{
printf("%8d",tmp.m[i][j]);
}
printf("\n");
}
}
void solve(mat res)
{
//print(res);
if(!res.m[0][si-1])
{
printf("False\n");
return ;
}
for(int i=1;i<si-1;i++)
{
if(res.m[0][i])
{
printf("Maybe\n");
return ;
}
}
printf("True\n");
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
getchar();
si = n*m;
memset(ans.m,0,sizeof(ans.m));
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
//printf("i = %d, j = %d\n",i,j);
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]);
getchar();
if(i== n-1 && j== m-1) continue;
int tmp1 = i*m + j;
for(int k=0;k<4;k++)
{
x[k]-- , y[k]--;
int tmp2 = m*x[k] + y[k];
ans.m[tmp1][tmp2] = 1;
}
}
}
//print(ans);
int q;
scanf("%d",&q);
while(q--)
{
int tmp;
scanf("%d",&tmp);
mat res = pow_mat(ans,tmp);
solve(res);
}
printf("\n");
}
}
嗯，这个图实际上就是对一个有向图，通过矩阵乘法实现一个坐标的变换，然后得到结果图去判断能否在指定步数内到达
