两只塔姆沃斯牛

题目描述

$10 \times 10$ 网格中有障碍物、John（F）和两头牛（C）。John 与牛初始均朝北，每分钟同时按相同规则移动：前方在界内且无障碍则前进一步，否则原地顺时针转 $90°$ 。若某分钟末在同一格则追捕结束，输出分钟数；若永远不会相遇，输出 $0$ 。

思路

两人运动完全确定，系统状态为（John 位置/朝向，牛位置/朝向），最多 $400 \times 400 = 16000$ 种。逐分钟模拟，分钟末同格则输出分钟数；若状态重复仍未相遇，说明进入循环，输出 $0$ 。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43#!/usr/bin/env python3
# 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-10-01 04:15
# update_at: 2026-10-04 15:00

import sys

# 方向编码：0 北 1 东 2 南 3 西，顺时针转 90 度就是 (d + 1) % 4
DIRS = ((-1, 0), (0, 1), (1, 0), (0, -1))


def step(r: int, c: int, d: int, grid: list[str]) -> tuple[int, int, int]:
    """按牛/John 的固定走法推进一步，返回新的 (行, 列, 方向)。

    前方无障碍且不出界就前进一步，否则原地顺时针转 90 度。
    """
    nr, nc = r + DIRS[d][0], c + DIRS[d][1]
    in_path = 0 <= nr < 10 and 0 <= nc < 10 and grid[nr][nc] != '*'
    return (nr, nc, d) if in_path else (r, c, (d + 1) % 4)


def solve() -> None:
    data = iter(sys.stdin.read().split())
    grid = [next(data) for _ in range(10)]  # 每行 10 个字符，不含空格，按 token 顺序消费
    # John、牛的初始 (行, 列)；两者初始都朝北
    f = next((r, c) for r in range(10) for c in range(10) if grid[r][c] == 'F') + (0,)
    c = next((r, c) for r in range(10) for c in range(10) if grid[r][c] == 'C') + (0,)

    seen: set = set()                   # (John 行,列,方向, 牛 行,列,方向)，共 16000 种
    while f[:2] != c[:2]:               # 分钟末同格才算抓住
        if (f, c) in seen:              # 状态重现仍未相遇 → 以后永远原样循环
            print(0)
            return
        seen.add((f, c))
        f = step(*f, grid)
        c = step(*c, grid)
    print(len(seen))                    # 每分钟登记一个状态，登记数就是经过的分钟数


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68// 两只塔姆沃斯牛（usaco-2.3.5 / 2035）
// 10x10 网格模拟：牛和 John 每步向前一格，撞墙/障碍则原地转向 90°。
// 两者每步最多 100 个位置 × 4 个朝向，模拟 400 步内不相遇即永不相遇。
#include <cstdio>

typedef long long ll;

const int N = 10;
const int STEPS = 400; // 位置(100)×朝向(4) 全状态只有 400 种

char g[N + 2][N + 2]; // 地图，边界设为障碍
int fx, fy, fdir;     // John 的位置与朝向
int cx, cy, cdir;     // 牛的位置与朝向

// 朝向：0 上，1 右，2 下，3 左
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

// 尝试向前走一格，撞障碍则原地转向 90°（顺时针）
void step(int &x, int &y, int &dir) {
    int nx = x + dx[dir];
    int ny = y + dy[dir];
    if (g[nx][ny] == '*') { // 前方是障碍，只转向不前进
        dir = (dir + 1) % 4;
    } else {
        x = nx;
        y = ny;
    }
}

int main() {
    // 边界设为障碍，简化越界判断
    for (int i = 0; i <= N + 1; i++) {
        g[0][i] = '*';
        g[N + 1][i] = '*';
        g[i][0] = '*';
        g[i][N + 1] = '*';
    }
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++) {
            scanf(" %c", &g[i][j]);
            if (g[i][j] == 'F') {
                fx = i;
                fy = j;
                g[i][j] = '.'; // John 离开后该格变空
            } else if (g[i][j] == 'C') {
                cx = i;
                cy = j;
                g[i][j] = '.';
            }
        }

    fdir = 0; // 都朝北出发
    cdir = 0;

    // 逐步模拟，最多 400 步（全状态数上限）
    for (int t = 1; t <= STEPS; t++) {
        step(fx, fy, fdir);
        step(cx, cy, cdir);
        if (fx == cx && fy == cy) { // 相遇
            printf("%d\n", t);
            return 0;
        }
    }
    // 400 步内未相遇，则状态进入循环，永不相遇
    printf("0\n");
    return 0;
}

目录

题目描述

思路

参考代码