整理的算法模板合集： ACM模板
三段题面，只有第三段是有用的…前两段又长单词又难懂，就是在讲故事。。。不过针对四种情况给出四个图帮助我们理解题意是真的赞，可能出题人怕我们看不懂吧（第一句话有好几个生词没见过让我怀疑这是不是英语 ）
题目大意就是一个n*m的矩阵，每一个格子上都有一个数字，我们可以从任意的点出发，每次向上下左右四个方向走，只能到有公共边的格子上去，求一共有多少条完整路径。
其中完整路径的定义是整条路上数字从1连续地走到n，其中如果到n了以后他的四个方向都没有n+1也就是不能继续往下走了才算到终点。（还有一个要求就是路径的长度必须大于等于4才算）
我们直接按照题意建图，把每一个点的四周能到的点连边，其中每一个点的编号就是(i - 1) * m + j，我们要求总的完整路径，由于这是一个DAG，很明显就是一个DAG上拓扑排序递推DP，所以我们直接建图以后拓扑排序，拓扑排序的过程中我们开始递推（实际上我们不用等拓扑排序以后再递推，在排序的过程中这个顺序已经是拓扑序了，已经没有了后效性）。
由于完整路径必须长度大于等于4，所以我们设立四个数组f[N][5]，其中f[x][1]表示以该点为起点（权值为1）的路径数f[x][2]表示的是权值为2，也就是是从起点走一步到达的地方的路径数，f[x][3]表示权值为3的路径数，f[x][4]表示的是以x为终点，权值（长度）大于等于4的路径数，我们用一个flag表示是否有路可走，一旦无路可走，我们答案就加上这个终点的f[x][4]的路径数（因为我们只算长度大于等于4的情况，短的路不算完整路径）。
千万注意初始化数组G，以免因为0和1导致连错边
int n, m; int head[N], ver[M], nex[M], tot; int f[N][5]; int in[N]; queue<int>q; int ans; int G[maxn][maxn]; void add(int x, int y) { ver[tot] = y; nex[tot] = head[x]; head[x] = tot ++ ; in[y] ++ ; } void toposort() { for(int i = 1; i <= n * m; ++ i){ if(!in[i]) q.push(i), f[i][1] = 1;//所有起点，赋值为1 } while(q.size()) { int x = q.front(); q.pop(); bool flag = true; for(int i = head[x]; ~i; i = nex[i]){ int y = ver[i]; in[y] -- ; f[y][2] = (f[y][2] + f[x][1]) % mod; f[y][3] = (f[y][3] + f[x][2]) % mod; f[y][4] = (f[y][4] + f[x][3] + f[x][4]) % mod; if(in[y] == 0) q.push(y); flag = false;//没有到终点 } if(flag)ans = (ans + f[x][4]) % mod; } } int main() { memset(head, -1, sizeof head); memset(G, 0x3f, sizeof G);//千万注意这个初始化 scanf("%d%d", &n, &m); for(int i = 1; i <= n; ++ i) for(int j = 1; j <= m; ++ j) scanf("%d", &G[i][j]); for(int i = 1; i <= n; ++ i) for(int j = 1; j <= m; ++ j){ int x, y = (i - 1) * m + j; if(i > 1) if(G[i - 1][j] == G[i][j] - 1) x = (i - 2) * m + j, add(x, y); if(j > 1) if(G[i][j - 1] == G[i][j] - 1) x = y - 1, add(x, y); if(i < n) if(G[i + 1][j] == G[i][j] - 1) x = y + m, add(x, y); if(j < m) if(G[i][j + 1] == G[i][j] - 1) x = y + 1, add(x, y); } toposort(); printf("%d", ans % mod); return 0; }