这道题是浙江省赛的中档题，虽然在同步赛上做了很长时间，依然没有坐出来。后来嵩哥说是矩阵乘法+log(p)，二分我还知道点，矩阵乘法就知之甚少了，然后这两天做了几个矩阵乘法的水题，算是有点了解了。
这道题给了一个有向图，每个节点出度最多为4，规定起点（1,1），终点（m，n），问能否在p步内到达，注意中间节点不能经过终点。p步后，如果只能到达终点，则输出“True”，不能到达输出“False”，其他情况输出“Maybe”。
首先构造出图的邻接矩阵，然后用矩阵乘法+log(p)便可求p次幂。最后判断Matrix[1][n]，若为假，则为“False”，为真，再判断Matrix[1][0…n-1]，若有一个为真为“Maybe”，其他为“True”。
PS：今天是2012/8/9，在训练赛中又出现了这道题目。心里暗自高兴，觉得可以做出这道题目，结果没做出来。
原因： 1.看到这题后，老想着以前怎么做的，没好好读题，想思路，结果题意还理解错了
2.以前做的时候对这道题也理解的不够深。
3.一道题目不是AC就可以了，也不是写出解题报告就可以了，而是真正理解这道题。
程序代码：
#include <iostream> #include <cstdio> #include <cstring> using namespace std; int mat[30][30], g[30][30], res[30][30]; int m, n, nm; void MatPow(int m1[][30], int m2[][30]) { int t[30][30]; for(int i = 0; i < nm - 1; i++) for(int j = 0; j < nm; j++){ t[i][j] = 0; for(int k = 0; k < nm - 1; k++) if(m1[i][k] && m2[k][j]){ t[i][j] = 1; break; } } memcpy(m1, t, sizeof(t)); } int main() { //freopen("input.txt", "r", stdin); int T; int Q, p; scanf("%d", &T); char s[100]; int X[5], Y[5]; while(T--){ scanf("%d %d\n", &m, &n); nm = m * n; memset(mat, 0, sizeof(mat)); for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ scanf("%s", s); sscanf(s, "((%d,%d),(%d,%d),(%d,%d),(%d,%d))", &X[0], &Y[0], &X[1], &Y[1], &X[2], &Y[2], &X[3], &Y[3]); for(int k = 0; k < 4; k++){ X[k]--; Y[k]--; mat[i * n + j][X[k] * n + Y[k]] = 1; } } } scanf("%d", &Q); while(Q--){ scanf("%d", &p); if(!p){ if(nm == 1) printf("True\n"); else printf("False\n"); continue; } bool ok = true; memcpy(g, mat, sizeof(g)); while(p){ if(p & 1){ if(ok){ memcpy(res, g, sizeof(g)); ok = false; }else MatPow(res, g); } p >>= 1; MatPow(g, g); } int ans = 0; for(int i = 0; i < nm - 1; i++){ if(res[0][i]){ ans++; } } if(res[0][nm - 1]){ if(ans == 0) printf("True\n"); else printf("Maybe\n"); }else printf("False\n"); } printf("\n"); } return 0; }
