洛谷P1518 [USACO2.4] 两只塔姆沃斯牛 The Tamworth Two 题解

题解

[P1518 [USACO2.4] 两只塔姆沃斯牛 The Tamworth Two]([P1518 USACO2.4] 两只塔姆沃斯牛 The Tamworth Two - 洛谷)
题意概述:

• 题目要求我们在一张大小固定的地图(边界+障碍物)里模拟人找牛的过程
  

题目分析:

• 题目本身题意简单,模拟的逻辑用上一个dx,dy数组即可很好实现
  
• 但是我一直在思考题目中说的如若人牛永远不相遇,则输出0,我想找一个限制条件来输出0,但是无从下手,是不是最后会循环回来,循环次数等等.这是我这道题目上思路卡的唯一地方,
  询问AI,AI是这样解释的,1. 设置最大步数阈值（最推荐，最简单）
  我们可以通过计算总状态数来确定一个安全上限。
  
  
  
  • Farmer John 的位置有 \(10 \times 10 = 100\) 种，方向有 \(4\) 种。
    
  • 牛的位置有 \(10 \times 10 = 100\) 种，方向有 \(4\) 种。
    
  • 总状态数 = \(100 \times 4 \times 100 \times 4 = 160,000\)。
    
  这意味着，如果模拟超过 \(160,000\) 次移动后两人还没相遇，他们必然已经进入了一个永远不会相遇的循环。在实际竞赛中，为了稳妥，我们通常设定一个略大一点的数字，比如 1,000,000。
  大概懂了吧,感觉是像高中时算概率的分母的所有情况数字,以后也学习以下这种估计的思路.
  
  
• 我的第一版代码,先判断了障碍物再判断了边界,这样由于||的短路机制,所以我的代码就会出现数组越界的情况(同样的,&&只要左边是 false，右边连看都不看。)
  

代码

[code]#include 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 s(10);        for(int i = 0; i < 10; ++i){                std::cin >> s;        }        std::pair c;        std::pair f;         for(int i = 0; i < 10; ++i){                for(int j = 0; j < 10; ++j){                        if(s[j] == 'C'){                                c.first = i;                                c.second = j;                        }                        if(s[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  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