3. 量子奶牛
题目ID：9733必做题100分
最新提交：
Accepted
100 分
历史最高：
Accepted
100 分
时间限制: 1000ms
空间限制: 524288kB
题目描述
约翰 T 秒前看到奶牛在 (x1,y1) 处，而现在看到奶牛在 (x2, y2) 处。毫无疑问，奶牛在这 T 秒内发生了量子隧穿效应。已知奶牛每秒可以移动一步到与当前格子四连通的格子处（除非目标格子处有障碍），现在约翰想知道奶牛有几种可能的隧穿路径。
（其实就是求从(x1,y1)走到(x2,y2)恰好过了 T 秒的路径数量）
输入格式
第一行包含 3个用空格隔开的整数 n，m，T。
接下来 n 行每行一个长度为 m 的字符串。‘.’ 是空地，'*'是障碍
最后一行 4 个整数 x1, y1, x2, y2。
输出格式
输出一行一个整数表示答案。
样例
Input 1
4 5 6
...*.
...*.
.....
.....
1 3 1 5
Output 1
1
样例解释
样例输入中，奶牛从(1,3)到(1,5)需要6秒，只有一种可能的路径。
数据范围
2≤N,M≤100，0<T<=15
思路
这题我乍一看这是一道很普通的dfs题目实则这就是一道dfs
但是请注意 这题是问我们有多少种可能的方案，所以快把你的vis删了吧！不然会WA的别问我咋知道的（
但是！！！
要加剪枝哦不然呐，难道就让你这么简单的过了？
错误示范
是错误的！！！！
#include<bits/stdc++.h>
using namespace std;
int a[100 + 20][100 + 20], n, m, t, qx, qy, zx, zy, sum;
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};
char ch;
bool cheak(int x, int y) {
return x >= 1 && x <= n && y >= 1 && y <= m;
}
void dfs(int x, int y, int nt) {
if (x == zx && y == zy && nt == t) {
sum++;
return ;
}
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (!cheak(nx, ny) || a[nx][ny]) {
continue;
}
dfs(nx, ny, nt + 1);
}
}
int main() {
//输入=）
return 0;
}
但先别急我们只要把这断剪枝加上去就行了哦
if (/*当前x与终点x的距离*/) +（/*当前y与终点y的距离*/） + /*当前时间*/ > /*规定时间*/) {
return ;[poll type=regular results=always chartType=pie]
}
此题解结……
这题解写的好吗？
- 好（那就再点个赞吧！）
- 一般般（QWQ）
- 不好（欢迎在评论区指出）
0
投票人