[USACO2.4] 两只塔姆沃斯牛 The Tamworth Two

GitHub跳转原题关系图返回列表

同时模拟牛和 Farmer 的位置与方向，用状态集合检测循环，若同格则输出分钟数。

OJ: luogu

题目 ID: P1518

难度:普及-

标签:模拟状态python

日期: 2026-07-15 21:48

目录

  1. 题意
  2. 思路
  3. Python 知识
  4. 代码
  5. 复杂度
  6. 总结

题意

在 10*10 网格中，牛和 Farmer 初始都朝北。每分钟二者同时行动：前方可走就前进一步，否则原地顺时针转 90 度。若某分钟结束后同格，输出分钟数；若永远不会相遇，输出 0。

思路

一个对象的状态由三部分组成：

text
行、列、方向

牛和 Farmer 的整体状态就是二者状态合在一起。网格和方向都是有限的，如果某个整体状态第二次出现，之后会完全重复，说明永远不会相遇。

所以流程是：

  1. 用 move(row, col, direction) 模拟单个对象移动一分钟；
  2. 每分钟前把整体状态放入 seen；
  3. 同时移动牛和 Farmer；
  4. 若同格，输出分钟数；
  5. 若状态重复，输出 0。

Python 知识

  • /home/rainboy/mycode/hugo-blog/content/program_language/python/collections_toolkit.md：set 适合记录访问过的状态。
  • /home/rainboy/mycode/hugo-blog/content/program_language/python/brute_force_validation.md：状态若含多个字段，可用元组保存并放入集合。
  • 方向数组 directions = [(-1,0),(0,1),(1,0),(0,-1)] 配合 (direction+1)%4 表示右转。
  • 0 <= nr < 10 是网格边界判断。

代码

python
directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]


def move(row, col, direction):
    dr, dc = directions[direction]
    nr = row + dr
    nc = col + dc

    if not (0 <= nr < 10 and 0 <= nc < 10) or grid[nr][nc] == "*":
        return row, col, (direction + 1) % 4
    return nr, nc, direction


grid = [input().strip() for _ in range(10)]

for r in range(10):
    for c in range(10):
        if grid[r][c] == "C":
            cow_row, cow_col = r, c
        elif grid[r][c] == "F":
            farmer_row, farmer_col = r, c

cow_direction = 0
farmer_direction = 0
seen = set()
minutes = 0

while True:
    state = (
        cow_row, cow_col, cow_direction,
        farmer_row, farmer_col, farmer_direction,
    )
    if state in seen:
        print(0)
        break
    seen.add(state)

    cow_row, cow_col, cow_direction = move(cow_row, cow_col, cow_direction)
    farmer_row, farmer_col, farmer_direction = move(
        farmer_row, farmer_col, farmer_direction
    )
    minutes += 1

    if cow_row == farmer_row and cow_col == farmer_col:
        print(minutes)
        break
cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */
#include <bits/stdc++.h>
using namespace std;

// 北、东、南、西
int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, 1, 0, -1};

char grid[10][11]; // 10x10 网格

// 状态总数：10*10*4 * 10*10*4 = 160000
bool vis[10][10][4][10][10][4];

// 尝试往当前方向走一步，如果被阻挡则转向
void move(int &r, int &c, int &dir) {
    int nr = r + dr[dir];
    int nc = c + dc[dir];
    // 越界或障碍物
    if (nr < 0 || nr >= 10 || nc < 0 || nc >= 10 || grid[nr][nc] == '*') {
        dir = (dir + 1) % 4; // 顺时针转 90 度
    } else {
        r = nr;
        c = nc;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 读入网格
    for (int i = 0; i < 10; i++) cin >> grid[i];

    int cr = 0, cc = 0, fr = 0, fc = 0; // 牛和 Farmer 的坐标
    // 找初始位置
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            if (grid[i][j] == 'C') { cr = i; cc = j; }
            if (grid[i][j] == 'F') { fr = i; fc = j; }
        }
    }

    int cd = 0, fd = 0; // 初始都朝北(0)
    int minutes = 0;

    while (1) {
        // 检查状态是否重复
        if (vis[cr][cc][cd][fr][fc][fd]) {
            cout << 0 << "\n";
            return 0;
        }
        vis[cr][cc][cd][fr][fc][fd] = true;

        // 牛和 Farmer 各走一步
        move(cr, cc, cd);
        move(fr, fc, fd);
        minutes++;

        // 相遇
        if (cr == fr && cc == fc) {
            cout << minutes << "\n";
            return 0;
        }
    }

    return 0;
}

复杂度

整体状态数最多为 10*10*4*10*10*4，时间和空间复杂度都是常数级。

总结

有限状态模拟题要主动记录状态。一旦状态重复，后续轨迹必然循环，可以安全判定无解。