写 "<=T" 18分,“==T” 100分,询问原因
查看原帖
写 "<=T" 18分,“==T” 100分,询问原因
1047162
蔡涵秋2011楼主2024/8/16 17:23

一下是我 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 分了。

而题目中“你的任务是计算出,一头在 TT 秒内从 (R1R_1, C1C_1) 移动到 (R2R_2, C2C_2)的奶牛可能经过的路径有哪些。" 难道不意味着询问“在 <= T 秒的时间里到达终点的可能性“吗?

请问是题目陈述不严谨还是我的代码有问题,又或是都有问题?

2024/8/16 17:23
加载中...