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

大宝和小宝 · 2025-07-21 19:44:31 · 题解

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

题意：

在一个 10^{2} 的方格内，农夫和牛每分钟动个一次，他们会沿着当前方向走直到遇到障碍物或越界，然后顺时针旋转 90 度。

终止条件：

• 农夫和牛在‌同一格‌相遇，输出‌相遇时间‌。
• 如果‌ 1000 分钟‌后仍未相遇，输出‌ 0‌。

解题思路：

1. 计算下一步的坐标

2. 检查是否‌越界‌或遇到‌障碍物‌：

   • 如果‌可以走‌，则更新位置。

   • 如果‌不能走‌，则‌顺时针旋转方向‌ cd = (cd + 1) % 4。

3. 检查‌是否相遇‌：

   • 如果相遇，直接返回当前时间。

   • 否则继续循环。

代码实现

一道模拟题 首先记录 F，C 的初始位置然后用方向数组储存四个方向的坐标变化。模拟循环 t=1 到 t=1000，并更新农夫和牛的位置。 最后检查一下边界就行了。

代码

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<string> v(10);
    int fx,fy,fd=0; // 农夫位置和方向
    int cx,cy,cd=0; // 牛的位置和方向
    // 读取输入并初始化位置
    for(int i=0;i<10;i++) {
        getline(cin,v[i]);
        for(int j=0; j<10;j++) {
            if(v[i][j]=='F') {
                fx=i;fy=j;
            }
            if(v[i][j]=='C') {
                cx=i;cy=j;
            }
        }
    }
    // 方向数组：北、东、南、西
    int dx[5]={-1,0,1,0};
    int dy[5]={0,1,0,-1};

    for(int t=1;t<=1000;t++) {
        // 农夫的移动
        int fxx=fx+dx[fd],fyy=fy+dy[fd];
        if(fxx>=0&&fxx<10&&fyy>=0&&fyy<10&&v[fxx][fyy]!='*') {
            fx=fxx;fy=fyy;
        } 
        else{
            fd=(fd+1)%4;
        }
        // 牛移动
        int cxx=cx+dx[cd],cyy=cy+dy[cd];
        if(cxx>=0&&cxx<10&&cyy>=0&&cyy<10&&v[cxx][cyy]!='*') {
            cx=cxx;cy=cyy;
        } 
        else{
            cd=(cd+1)%4;
        }
        if(fx==cx&&fy==cy) {
            cout<<t<<endl;
            return 0;
        }
    }
    cout<<0<<endl;
    return 0;
}