行业资讯
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......* ...*.*.... .*.*......输出 #149说明/提示翻译来自NOCOWUSACO 2.4解题思路本题是网格同步模拟 状态循环检测的经典题目通过逐分钟严格复现移动规则结合有限状态的去重机制判定是否永远无法相遇最终得到追捕结果。1. 移动规则梳理牛与 Farmer John 遵循完全一致的移动逻辑初始方向均为正北方向按顺时针顺序分为四档北向上、东向右、南向下、西向左。每分钟执行一次动作尝试沿当前方向前进一步若目标格在地图范围内且不是障碍物则成功移动位置。若前方无法通行越界或遇障碍物则原地顺时针旋转 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×4160000是有限值。根据鸽巢原理若模拟过程中出现重复状态说明系统进入周期循环永远不会相遇此时直接输出 0 即可终止模拟。3. 模拟执行流程初始化读取 10 行地图记录牛和 John 的初始坐标将起始位置的字符改为空地不影响后续通行判断双方初始方向均设为正北。逐分钟循环检查当前状态是否已出现过出现过则判定永不相遇输出 0 并结束。标记当前状态为已访问。时间计数加 1分别按规则更新牛和 John 的位置/方向。移动完成后判断两者坐标是否重合重合则输出当前时间并结束程序。4. 复杂度分析总状态数不超过 16 万单次状态处理为常数级操作运行时间极短远低于 1 秒时间限制。总结核心逻辑严格按照题目规则同步模拟两者的移动行为通过多维状态数组记录历史状态出现重复则判定进入死循环永不相遇否则直到位置重合输出对应分钟数。关键操作方向数组定义位移、顺时针转向模 4 处理、状态去重防止死循环、同步移动后统一判定相遇。效率保障状态总数仅十万级模拟步数有明确上限无任何性能压力。代码简要说明全局变量定义cx, cy, cd牛的行、列坐标与当前方向jx, jy, jdFarmer John 的行、列坐标与当前方向。fx、fy方向偏移数组按北、东、南、西顺序排列对应每个方向的行列变化量。mp二维字符数组存储 10×10 的网格地图信息。vis六维布尔数组记录「牛位置 John 位置 双方方向」的组合状态是否已出现过用于循环检测。移动函数movecows与movejohn两者逻辑完全一致先计算沿当前方向前进后的目标坐标。若目标坐标在 1~10 范围内且对应格子不是障碍物则更新坐标完成移动。若无法移动则方向值加 1 并对 4 取模实现顺时针旋转 90 度。主函数初始化逐行逐列读取地图字符遇到F和C时记录对应初始坐标并将该格子改为空地。时间计数器minu初始化为 0对应第 0 分钟的初始状态。模拟主循环进入循环先校验当前状态是否已访问是则输出 0 并结束。标记当前状态为已访问时间计数加 1。分别调用两个移动函数同步更新双方的位置与方向。检查两者坐标是否完全重合重合则输出当前分钟数并终止循环。输入优化关闭流同步并解绑 tie提升地图数据的读取效率。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;constll MAXN15;constll INF20x3f3f3f3f;constdoubleEPS1e-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 txcxfx[cd];ll tycyfy[cd];if(tx1tx10ty1ty10mp[tx][ty]!*){cxtx;cyty;}else{cd;cd%4;}}voidmovejohn(){ll txjxfx[jd];ll tyjyfy[jd];if(tx1tx10ty1ty10mp[tx][ty]!*){jxtx;jyty;}else{jd;jd%4;}}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);for(ll i1;i10;i){for(ll j1;j10;j){cinmp[i][j];if(mp[i][j]F){mp[i][j].;jxi;jyj;}elseif(mp[i][j]C){mp[i][j].;cxi;cyj;}}}ll minu0;while(1){if(vis[cx][cy][jx][jy][cd][jd]){cout0endl;break;}vis[cx][cy][jx][jy][cd][jd]1;minu;movecows();movejohn();if(cxjxcyjy){coutminuendl;break;}}return0;}
郑州网站建设
网页设计
企业官网
