洛谷P1518 [USACO2.4] 两只塔姆沃斯牛 The Tamworth Two 题解
题目分析:
题目本身题意简单,模拟的逻辑用上一个dx,dy数组即可很好实现
但是我一直在思考题目中说的如若人牛永远不相遇,则输出0,我想找一个限制条件来输出0,但是无从下手,是不是最后会循环回来,循环次数等等.这是我这道题目上思路卡的唯一地方,
询问AI,AI是这样解释的,1. 设置最大步数阈值（最推荐，最简单）
我们可以通过计算总状态数来确定一个安全上限。
- Farmer John 的位置有 10×10=100 种，方向有 4 种。
- 牛的位置有 10×10=100 种，方向有 4 种。
- 总状态数= 100×4×100×4=160,000。
这意味着，如果模拟超过 160,000 次移动后两人还没相遇，他们必然已经进入了一个永远不会相遇的循环。在实际竞赛中，为了稳妥，我们通常设定一个略大一点的数字，比如
1,000,000。大概懂了吧,感觉是像高中时算概率的分母的所有情况数字,以后也学习以下这种估计的思路.
我的第一版代码,先判断了障碍物再判断了边界,这样由于||的短路机制,所以我的代码就会出现数组越界的情况(同样的,&&只要左边是
false，右边连看都不看。)
代码
#include <bits/stdc++.h> using i64 = long long; int dx[] = {-1,0,1,0}; int dy[] = {0,1,0,-1}; int da[] = {-1,0,1,0}; int db[] = {0,1,0,-1}; void solve(){ std::vector<std::string> s(10); for(int i = 0; i < 10; ++i){ std::cin >> s[i]; } std::pair<int,int> c; std::pair<int,int> f; for(int i = 0; i < 10; ++i){ for(int j = 0; j < 10; ++j){ if(s[i][j] == 'C'){ c.first = i; c.second = j; } if(s[i][j] == 'F'){ f.first = i; f.second = j; } } } auto &[x,y] = c; auto &[a,b] = f; int fx = 0; int fx1 = 0; int m1 = 0; i64 mmax = 160000; while(c != f){ if(m1 > mmax){ std::cout << 0; return; } int nx = x + dx[fx]; int ny = y + dy[fx]; if(nx < 0 || nx > 9 || ny < 0|| ny > 9){ fx += 1; fx %= 4; } else { if(s[nx][ny] == '*'){ fx += 1; fx %= 4; } else{ x = nx; y = ny; } } int na = a + da[fx1]; int nb = b + db[fx1]; if(na < 0 || na > 9 || nb < 0|| nb > 9){ fx1 += 1; fx1 %= 4; } else { if(s[na][nb] == '*'){ fx1 += 1; fx1 %= 4; } else{ a = na; b = nb ; } } ++m1; } std::cout << m1; } int main(){ std::ios::sync_with_stdio(false); std::cin.tie(nullptr); solve(); return 0; }