一下是我 AC 的代码(附注释):
#include <bits/stdc++.h>
#define int long long
using namespace std;
char mp[105][105];//地图,记录草和树
int N, M, T, R1, C1, R2, C2, ans[105][105][20];
//N,M 是草场的长和宽,T 是所需的时间
//R1 和 C1 是起点,R2 和 C2 是终点
//ans[x][y][sec] 指在第 sec 秒 (x, y) 是去终点的方式数量
int mx[] = {0, 0, 1, -1};
int my[] = {1, -1, 0, 0};
int dfs(int x, int y, int sec)
{
if (x < 1 || x > N) return 0;
else if (y < 1 || y > M) return 0;
//以上判断是否越界
else if (ans[x][y][sec]) return ans[x][y][sec];
//如果被计算过就直接 return
else if (mp[x][y] == '*') return ans[x][y][sec] = 0;
//是树也不能走
else if (sec > T) return ans[x][y][sec] = 0;
//时间超过了也不行
else if (abs(R2 - x) + abs(C2 - y) > T - sec) return ans[x][y][sec] = 0;
//如果要走的路程所花时间大于剩下的时间,没有可能
else if (sec == T && x == R2 && y == C2) return ans[x][y][sec] = 1;
//到达终点,返回 1
for (int i = 0; i < 4; i++)
ans[x][y][sec] += dfs(x + mx[i], y + my[i], sec + 1);
//加上“上下左右”四种可能性
return ans[x][y][sec];
//返回结果
}
signed main()
{
cin >> N >> M >> T;
for (int i = 1; i <= N; i++)
cin >> (mp[i] + 1);
cin >> R1 >> C1 >> R2 >> C2;
//以上是输入
cout << dfs(R1, C1, 0);
//输出答案
return 0;
}
当我把第 26 行的 sec == T 改为 sec <= T 就只有 18 分了。
而题目中“你的任务是计算出,一头在 T 秒内从 (R1, C1) 移动到 (R2, C2)的奶牛可能经过的路径有哪些。" 难道不意味着询问“在 <= T 秒的时间里到达终点的可能性“吗?
请问是题目陈述不严谨还是我的代码有问题,又或是都有问题?