P1535 [USACO08MAR] Cow Travelling S
读题
P1535 [USACO08MAR] Cow Travelling S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目大概意思是说,奶牛在一个给定大小的矩形范围内走,地块有两种:草地或者树,其中树奶牛不能走。
奶牛一次可以上下左右走,不能原地不动(但是可以绕圈!),给定两个点A,B,求出奶牛从A到B的步数为T的路径总数。
这里原题表述有些问题,不知道是不是翻译的不清楚,原文说的是“在 T 秒内”,但是实际上就看的是T秒这一秒。害得我半天没找出毛病,还是看讨论版才发现的
思路
最早想的是用BFS来搜索,直到队首元素的时间到t+1位置。但是试了一下就报MLE了
教程 / 题解