P1518 两只塔姆沃斯牛 The Tamworth Two【洛谷算法习题】-育师

P1518 两只塔姆沃斯牛 The Tamworth Two

网页链接

P1518 两只塔姆沃斯牛 The Tamworth Two

题目描述

两只牛逃跑到了森林里。Farmer John 开始用他的专家技术追捕这两头牛。你的任务是模拟他们的行为（牛和 John）。

追击在10 × 10 10 \times 1010×10的平面网格内进行。一个格子可以是：空地，一个障碍物，两头牛（它们总在一起），或者 Farmer John。两头牛和 Farmer John 可以在同一个格子内（当他们相遇时），但是他们都不能进入有障碍的格子。

一个格子可以是：

.空地；
*障碍物；
C两头牛；
FFarmer John。

这里有一个地图的例子：

*...*..... ......*... ...*...*.. .......... ...*.F.... *.....*... ...*...... ..C......* ...*.*.... .*.*......

牛在地图里以固定的方式游荡。每分钟，它们可以向前移动或是转弯。如果前方无障碍（地图边沿也是障碍），它们会按照原来的方向前进一步。否则它们会用这一分钟顺时针转90 9090度。同时，它们不会离开地图。

Farmer John 深知牛的移动方法，他也这么移动。

每次（每分钟）Farmer John 和两头牛的移动是同时的。如果他们在移动的时候穿过对方，但是没有在同一格相遇，我们不认为他们相遇了。当他们在某分钟末在某格子相遇，那么追捕结束。

读入十行表示地图。每行都只包含10 1010个字符，表示的含义和上面所说的相同。保证地图中只有一个F和一个C。F和C一开始不会处于同一个格子中。

计算 Farmer John 需要多少分钟来抓住他的牛，假设牛和 Farmer John 一开始的行动方向都是正北（即上）。如果 John 和牛永远不会相遇，输出0 00。

输入格式

输入共十行，每行10 1010个字符，表示如上文描述的地图。

输出格式

输出一个数字，表示 John 需要多少时间才能抓住牛们。如果 John 无法抓住牛，则输出0 00。

输入输出样例 #1

输入 #1

*...*..... ......*... ...*...*.. .......... ...*.F.... *.....*... ...*...... ..C......* ...*.*.... .*.*......

输出 #1

说明/提示

翻译来自NOCOW

USACO 2.4

解题思路

本题是网格同步模拟 + 状态循环检测的经典题目，通过逐分钟严格复现移动规则，结合有限状态的去重机制判定是否永远无法相遇，最终得到追捕结果。

1. 移动规则梳理

牛与 Farmer John 遵循完全一致的移动逻辑，初始方向均为正北：

方向按顺时针顺序分为四档：北（向上）、东（向右）、南（向下）、西（向左）。
每分钟执行一次动作：
1. 尝试沿当前方向前进一步，若目标格在地图范围内且不是障碍物，则成功移动位置。
2. 若前方无法通行（越界或遇障碍物），则原地顺时针旋转 90 度，不改变位置。
两者同时移动，仅当每分钟结束后处于同一格子才算相遇，移动途中擦肩而过不计入相遇。

2. 循环检测原理

整个系统的完整状态由「牛的坐标 + 牛的方向 + John 的坐标 + John 的方向」共同决定。
网格为 10×10，方向共 4 种，因此总状态数为10 × 10 × 4 × 10 × 10 × 4 = 160000 10 \times 10 \times 4 \times 10 \times 10 \times 4 = 16000010×10×4×10×10×4=160000，是有限值。
根据鸽巢原理，若模拟过程中出现重复状态，说明系统进入周期循环，永远不会相遇，此时直接输出 0 即可终止模拟。

3. 模拟执行流程

初始化：读取 10 行地图，记录牛和 John 的初始坐标，将起始位置的字符改为空地（不影响后续通行判断），双方初始方向均设为正北。
逐分钟循环：
- 检查当前状态是否已出现过，出现过则判定永不相遇，输出 0 并结束。
- 标记当前状态为已访问。
- 时间计数加 1，分别按规则更新牛和 John 的位置/方向。
- 移动完成后判断两者坐标是否重合，重合则输出当前时间并结束程序。

4. 复杂度分析

总状态数不超过 16 万，单次状态处理为常数级操作，运行时间极短，远低于 1 秒时间限制。

总结

核心逻辑：严格按照题目规则同步模拟两者的移动行为，通过多维状态数组记录历史状态，出现重复则判定进入死循环永不相遇，否则直到位置重合输出对应分钟数。
关键操作：方向数组定义位移、顺时针转向模 4 处理、状态去重防止死循环、同步移动后统一判定相遇。
效率保障：状态总数仅十万级，模拟步数有明确上限，无任何性能压力。

代码简要说明

全局变量定义
- cx, cy, cd：牛的行、列坐标与当前方向；jx, jy, jd：Farmer John 的行、列坐标与当前方向。
- fx、fy方向偏移数组：按北、东、南、西顺序排列，对应每个方向的行列变化量。
- mp二维字符数组：存储 10×10 的网格地图信息。
- vis六维布尔数组：记录「牛位置 + John 位置 + 双方方向」的组合状态是否已出现过，用于循环检测。
移动函数movecows与movejohn
- 两者逻辑完全一致：先计算沿当前方向前进后的目标坐标。
- 若目标坐标在 1~10 范围内且对应格子不是障碍物，则更新坐标完成移动。
- 若无法移动，则方向值加 1 并对 4 取模，实现顺时针旋转 90 度。
主函数初始化
- 逐行逐列读取地图字符，遇到F和C时记录对应初始坐标，并将该格子改为空地。
- 时间计数器minu初始化为 0，对应第 0 分钟的初始状态。
模拟主循环
- 进入循环先校验当前状态是否已访问，是则输出 0 并结束。
- 标记当前状态为已访问，时间计数加 1。
- 分别调用两个移动函数，同步更新双方的位置与方向。
- 检查两者坐标是否完全重合，重合则输出当前分钟数并终止循环。
输入优化：关闭流同步并解绑 tie，提升地图数据的读取效率。

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;constll MAXN=15;constll INF2=0x3f3f3f3f;constdoubleEPS=1e-8;ll cx,cy,cd,jx,jy,jd;ll fx[4]={-1,0,1,0};ll fy[4]={0,1,0,-1};charmp[MAXN][MAXN];boolvis[MAXN][MAXN][MAXN][MAXN][5][5];voidmovecows(){ll tx=cx+fx[cd];ll ty=cy+fy[cd];if(tx>=1&&tx<=10&&ty>=1&&ty<=10&&mp[tx][ty]!='*'){cx=tx;cy=ty;}else{cd++;cd%=4;}}voidmovejohn(){ll tx=jx+fx[jd];ll ty=jy+fy[jd];if(tx>=1&&tx<=10&&ty>=1&&ty<=10&&mp[tx][ty]!='*'){jx=tx;jy=ty;}else{jd++;jd%=4;}}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);for(ll i=1;i<=10;i++){for(ll j=1;j<=10;j++){cin>>mp[i][j];if(mp[i][j]=='F'){mp[i][j]='.';jx=i;jy=j;}elseif(mp[i][j]=='C'){mp[i][j]='.';cx=i;cy=j;}}}ll minu=0;while(1){if(vis[cx][cy][jx][jy][cd][jd]){cout<<0<<endl;break;}vis[cx][cy][jx][jy][cd][jd]=1;minu++;movecows();movejohn();if(cx==jx&&cy==jy){cout<<minu<<endl;break;}}return0;}