王梓涵
( 梦幻の幸运使者 qwq)
1
#include<bits/stdc++.h>
using namespace std;
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
char mp[105][105];
int vis[105][105]={0};
int n,m,t,cnt,A,B,C,D;
int step;
void dfs(int x,int y);
int main(){
// ios_base::sync_with_stdio(false);
// cin.tie(NULL);
cin>>n>>m>>t;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>mp[i][j];
}
}
cin>>A>>B>>C>>D;
vis[A][B]=1;
dfs(A,B);
cout<<cnt;
return 0;
}
void dfs(int x,int y){
if(step>t){
step=0;
return;
}
if(x==C&&y==D){
if(step==t){
step=0;
cnt++;
}
return;
}
for(int i=0;i<4;i++)
{
int nx=x+dx[i];
int ny=y+dy[i];
if(nx<1||nx>n||ny<1||ny>m||mp[nx][ny]=='*'||vis[nx][ny])
{
continue;
}
vis[nx][ny]=1;
step++;
dfs(nx,ny);
vis[nx][ny]=0;
}
}
这怎么加剪枝
1 个赞
王梓涵
( 梦幻の幸运使者 qwq)
2
题目：
奶牛们在被划分成 N 行 M 列 (2 <= N <= 100; 2 <= M <= 100) 的草地上游走， 试图找到整块草地中最美味的牧草。Farmer John 在某个时刻看见贝茜在位置 (R1, C1)，恰好 T(0 < T <= 15) 秒后，FJ 又在位置 (R2, C2) 与贝茜撞了正着。 FJ 并不知道在这 T 秒内贝茜是否曾经到过 (R2, C2)，他能确定的只是现在贝茜在那里。设 S 为奶牛在 T 秒内从 (R1, C1) 走到 (R2, C2) 所能选择的路径总数，FJ 希望有 一个程序来帮他计算这个值。
每一秒内，奶牛会水平或垂直地移动 1 单位距离（奶牛总是在移动，不会在某秒内停在它上一秒所在的点）。草地上的某些地方有树，自然，奶牛不能走到树所在的位置，也不会走出草地。
现在你拿到了一张整块草地的地形图，其中 '.' 表示平坦的草地，'*' 表示 挡路的树。你的任务是计算出，一头在 T 秒内从 (R1, C1) 移动到 (R2, C2) 的奶牛可能经过的路径有多少。
输入格式：
第 1 行: 3 个用空格隔开的整数：N，M，T 。
第 2...N+1 行: 第 i+1 行为 M 个连续的字符，描述了草地第 i 行各点的情况，保证字符是 '.' 和 '*' 中的一个。
第 N+2 行: 4 个用空格隔开的整数：R1，C1，R2，C2 。
输出格式：
第1 行: 输出S，含义如题中所述。
样例输入1：
4 5 6
...*.
...*.
.....
.....
1 3 1 5
样例输出1：
1
1 个赞
方悦丞
(初音ミク)
5
这道题目用BFS来做的话，
因为是求方案数，所以对于每一个走过的点，我们不能常规化的打上标记，以后不走，
而是应该考虑记忆化搜索，用f[i][j][k]表示第k秒到达点(i,j)的方案数，
不难发现，如果f[i][j][k]不为0，那么它四周的点是不可能在第k秒到达的，
所以我们只需要知道它四周的点的f[i][j][k-1]，一步步递推下去就可以了。
1 个赞
方悦丞
(初音ミク)
17
所以可以增加这个：
if (step+abs(x-C)+abs(y-D)>t) return ;//如果路程比体力多，那么肯定不行，直接Return
1 个赞
