时间限制: 1.0s??内存限制: 256.0MB? 小蓝在玩一个叫质数行者的游戏。 游戏在一个n×m×wn×m×w在立体方格图上，从北到南依次标注第一11行到 第nn行，从西到东依次标注11列到第mm列，从下到上依次标注第一11层到 第ww层。 小蓝应该从头开始控制自己的角色11行第11列第11层移动到第nn行第mm列第ww层。 小蓝应该从头开始控制自己的角色11行第11列第11层移动到第nn行第mm列第ww层。每一步，他都可以向东、向南或向上。每走到 在一个位置，小蓝的角色应该停留一点。 游戏中有两个陷阱，分别是第一个r1r1行第c1c1列第h1h1层和第r2r2行第c2c2列第h2h2层。这两个陷阱的位置可以跨越，但不能停留。换句话说，小蓝控制不了角 色某一步正好走到陷阱上，但允许某一步中间跨过陷阱。 小兰最近很闲，所以他想用不同的方式完成游戏。所谓两个走路 不同的方法意味着小蓝停留在不同的位置。 请帮小兰计算一下他有多少种不同的走法。 提示：请注意内存限制，如果您的程序超过内存限制，则不得分。 第一行包含两个整数n,m,wn,m,w，表示方格图的大小。 第二行包含 6 个整数，r1,c1,h1,r2,c2,h2r1,c1,h1,r2,c2,h2.表示陷阱的位置。 一行输出，包一个整数，表示行走的数量。答案可能很大，请输出答案 案除以10000000071000000007的余数。 对于300%的评测用例1≤n,m,w≤501≤n,m,w≤50。 对于60`%的评测用例1≤n,m,w≤3001≤n,m,w≤300。 对于所有评估用例，1≤n,m,w≤1000，1≤r1,r2≤n,1≤c1,c2≤m,1≤h1,h2≤w1≤n,m,w≤1000，1≤r1,r2≤n,1≤c1,c2≤m,1≤h1,h2≤w，陷阱不在起点或终点，两个陷阱不同。
只能成功40%
#include<iostream> #include<algorithm> using namespace std; const int MOD = 1000000007; int dp[303][303][303]; int p[1001]; int main() { int n, m, w; cin >> n >> m >> w; int r1, c1, h1, r2, c2, h2; cin >> r1 >> c1 >> h1; cin >> r2 >> c2 >> h2; int Max = max(n, m); Max = max(Max, w); dp[1][1][1] = 1; int u = 1; for (int i = 2; i <= Max; i ) { ///确定质数 bool flag = true; for (int j = 2; j < i; j ) { if (i % j == 0) { flag = false; break; } } if (flag) { p[u ] = i; } } for (int i = 1; i <= n; i ) { for (int j = 1; j <= m; j ) { for (int k = 1; k <= w; k ) { if (i == r1 && j == c1 && k == h1) continue; if (i == r2 && j == c2 && k == h2) continue; for (int l = 1; l < u; l ) { if (i - p[l] >= 0) dp[i][j][k] = (dp[i][j][k] dp[i - p[l]][j][k]) % MOD; else break; } for (int l = 1; l < u; l ) { if (j - p[l] >= 0) dp[i][j][k] = (dp[i][j][k] dp[i][j - p[l]][k]) % MOD; else break; } for (int l = 1; l < u; l ) { if (k - p[l] >= 0) dp[i][j][k] = (dp[i][j][k] dp[i][j][k - p[l]]) % MOD; else break; } } } } cout << dp[n][m][w] << endl; return 0; }