A40200. 质数行者
题目描述
质数行者
题目描述
小蓝在玩一个叫质数行者的游戏，游戏在一个 n × m × w的立体方格图上进行，
从北到南依次标号为第 1 行到第n行，从西到东依次标号为第 1 列到第 m列，从下到上依次标号为第 1 层到第 w层。
小蓝要控制自己的角色从第 1 行第 1 列第 1 层移动到第 n 行第 m列第 w层。
每一步，他可以向东走质数格、向南走质数格或者向上走质数格，每走到一个位置，小蓝的角色要稍作停留。
在游戏中有两个陷阱，分别为第 r 1 行第 c 1 列第 h 1层和第 r 2 行第 c 2 列第 h 2 层，这两个陷阱可以跨过，但不能停留。
也就是说，小蓝不能控制角色某一步正好走到陷阱上，但是某一步中间跨过了陷阱是允许的。
小蓝最近比较清闲，因此他想用不同的走法来完成这个游戏。所谓两个走法不同，是指小蓝稍作停留的位置集合不同。
请帮小蓝计算一下，他总共有多少种不同的走法。
提示：请注意内存限制，如果你的程序运行时超过内存限制将不得分。
输入格式
输入第一行包含两个整数 n , m , w 表示方格图的大小。
第二行包含 6 66 个整数，r 1 , c 1 , h 1 , r 2 , c 2 , h 2 表示陷阱的位置。
输出格式
输出一行，包含一个整数，表示走法的数量。答案可能非常大，请输出答案除以1000000007的余数。
样例输入
5 6 1
3 4 1 1 2 1
样例输出
11
样例说明
用 ( r , c , h ) (r,c,h)(r,c,h) 表示第 r rr 行第 c cc 列第 h hh 层，可能的走法有以下几种：
( 1 , 1 , 1 ) − ( 1 , 3 , 1 ) − ( 1 , 6 , 1 ) − ( 3 , 6 , 1 ) − ( 5 , 6 , 1 ) (1,1,1) − (1,3,1) − (1,6,1) − (3,6,1) − (5,6,1)(1,1,1)−(1,3,1)−(1,6,1)−(3,6,1)−(5,6,1)
( 1 , 1 , 1 ) − ( 1 , 3 , 1 ) − ( 3 , 3 , 1 ) − ( 3 , 6 , 1 ) − ( 5 , 6 , 1 ) (1,1,1) − (1,3,1) − (3,3,1) − (3,6,1) − (5,6,1)(1,1,1)−(1,3,1)−(3,3,1)−(3,6,1)−(5,6,1)
( 1 , 1 , 1 ) − ( 1 , 3 , 1 ) − ( 3 , 3 , 1 ) − ( 5 , 3 , 1 ) − ( 5 , 6 , 1 ) (1,1,1) − (1,3,1) − (3,3,1) − (5,3,1) − (5,6,1)(1,1,1)−(1,3,1)−(3,3,1)−(5,3,1)−(5,6,1)
( 1 , 1 , 1 ) − ( 3 , 1 , 1 ) − ( 3 , 3 , 1 ) − ( 3 , 6 , 1 ) − ( 5 , 6 , 1 ) (1,1,1) − (3,1,1) − (3,3,1) − (3,6,1) − (5,6,1)(1,1,1)−(3,1,1)−(3,3,1)−(3,6,1)−(5,6,1)
( 1 , 1 , 1 ) − ( 3 , 1 , 1 ) − ( 3 , 3 , 1 ) − ( 5 , 3 , 1 ) − ( 5 , 6 , 1 ) (1,1,1) − (3,1,1) − (3,3,1) − (5,3,1) − (5,6,1)(1,1,1)−(3,1,1)−(3,3,1)−(5,3,1)−(5,6,1)
( 1 , 1 , 1 ) − ( 3 , 1 , 1 ) − ( 5 , 1 , 1 ) − ( 5 , 3 , 1 ) − ( 5 , 6 , 1 ) (1,1,1) − (3,1,1) − (5,1,1) − (5,3,1) − (5,6,1)(1,1,1)−(3,1,1)−(5,1,1)−(5,3,1)−(5,6,1)
( 1 , 1 , 1 ) − ( 3 , 1 , 1 ) − ( 5 , 1 , 1 ) − ( 5 , 4 , 1 ) − ( 5 , 6 , 1 ) (1,1,1) − (3,1,1) − (5,1,1) − (5,4,1) − (5,6,1)(1,1,1)−(3,1,1)−(5,1,1)−(5,4,1)−(5,6,1)
( 1 , 1 , 1 ) − ( 1 , 4 , 1 ) − ( 1 , 6 , 1 ) − ( 3 , 6 , 1 ) − ( 5 , 6 , 1 ) (1,1,1) − (1,4,1) − (1,6,1) − (3,6,1) − (5,6,1)(1,1,1)−(1,4,1)−(1,6,1)−(3,6,1)−(5,6,1)
( 1 , 1 , 1 ) − ( 1 , 6 , 1 ) − ( 3 , 6 , 1 ) − ( 5 , 6 , 1 ) (1,1,1) − (1,6,1) − (3,6,1) − (5,6,1)(1,1,1)−(1,6,1)−(3,6,1)−(5,6,1)
( 1 , 1 , 1 ) − ( 3 , 1 , 1 ) − ( 3 , 6 , 1 ) − ( 5 , 6 , 1 ) (1,1,1) − (3,1,1) − (3,6,1) − (5,6,1)(1,1,1)−(3,1,1)−(3,6,1)−(5,6,1)
( 1 , 1 , 1 ) − ( 3 , 1 , 1 ) − ( 5 , 1 , 1 ) − ( 5 , 6 , 1 ) (1,1,1) − (3,1,1) − (5,1,1) − (5,6,1)(1,1,1)−(3,1,1)−(5,1,1)−(5,6,1)
数据范围
对于 30% 的评测用例， 1 ≤ n , m , w ≤ 50 。 1 ≤ n,m,w ≤ 50。1≤n,m,w≤50。
对于 60% 的评测用例， 1 ≤ n , m , w ≤ 300 。 1 ≤ n,m,w ≤ 300。1≤n,m,w≤300。
对于所有评测用例，1 ≤ n , m , w ≤ 1000 ， 1 ≤ r 1 , r 2 ≤ n , 1 ≤ c 1 , c 2 ≤ m , 1 ≤ h 1 , h 2 ≤ w 1 ≤ n,m,w ≤ 1000，1 ≤ r 1 ,r 2 ≤ n, 1 ≤ c 1 ,c 2 ≤ m, 1 ≤ h 1 ,h 2 ≤ w1≤n,m,w≤1000，1≤r1,r2≤n,1≤c1,c2≤m,1≤h1,h2≤w，陷阱不在起点或终点，两个陷阱不同。
参考答案
#include<bits/stdc++.h>
using namespace std;
const int N=3e2+5,mod=1e9+7;
int e[N][N][N],vis2[N][N][N];
int n,m,w,r1,c1,h1,r2,c2,h2,cot;
int prime[N],vis[N],res;
void prime_(int x)
{
for(int i=2;i<=x;i++){
if(!vis[i]){
prime[cot++]=i;
for(int j=2*i;j<=x;j+=i)
vis[j]=1;
}
}
}
bool check(int x,int y,int h)
{
if(x==r1&&y==c1&&h==h1)return false;
if(x==r2&&y==c2&&h==h2)return false;
return true;
}
void print_()//打印路径
{
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
for(int k=1;k<=w;k++)
if(vis2[i][j][k]==1)
cout<<i<<','<<j<<','<<k<<'-';
cout<<'\n';
}
void dfs(int x,int y,int h)
{
if(x==n&&y==m&&h==w){
res=(res+1)%mod;
//print_();//打印路径
return ;
}
for(int i=0;i<cot;i++){
if(x+prime[i]<=n&&check(x+prime[i],y,h)){
vis2[x+prime[i]][y][h]=1;
dfs(x+prime[i],y,h);
vis2[x+prime[i]][y][h]=0;
}
if(y+prime[i]<=m&&check(x,y+prime[i],h)){
vis2[x][y+prime[i]][h]=1;
dfs(x,y+prime[i],h);
vis2[x][y+prime[i]][h]=0;
}
if(h+prime[i]<=h&&check(x,y,h+prime[i])){
vis2[x][y][h+prime[i]]=1;
dfs(x,y,h+prime[i]);
vis2[x][y][h+prime[i]]=0;
}
}
}
int main()
{
cin>>n>>m>>w;
cin>>r1>>c1>>h1>>r2>>c2>>h2;
int maxx=max(max(n,m),w);
prime_(maxx);
vis2[1][1][1]=1;
dfs(1,1,1);
vis2[1][1][1]=0;
cout<<res<<'\n';
return 0;
}
/*
5 6 1
3 4 1 1 2 1
*/