本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P1518 [USACO2.4] 两只塔姆沃斯牛 The Tamworth Two - 洛谷luogu.com.cn)【题目描述】两只牛逃跑到了森林里。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。【输入样例】*...*..... ......*... ...*...*.. .......... ...*.F.... *.....*... ...*...... ..C......* ...*.*.... .*.*......【输出样例】49【核心思想】问题分析给定10 × 10 10 \times 1010×10网格地图农夫F和两头牛C初始方向均为正北。每分钟两者同时移动若前方可通行则前进一格否则顺时针转90 ∘ 90^\circ90∘。求两者相遇所需的最少分钟数若永远不会相遇则输出0 00。这是一个状态模拟 循环检测问题。算法选择逐分钟模拟按照规则同时移动农夫和牛每分钟更新一次位置六维状态标记用mark[fx][fy][ff][cx][cy][cf]记录状态位置方向若状态重复则说明进入循环永远无法相遇关键步骤读入地图10 × 10 10 \times 1010×10字符网格标记障碍物*、空地.、牛C、农夫F初始化状态找到C和F的初始位置方向均设为0 00北地图数组m[i][j]障碍物为0 00可通行为1 11模拟循环每分钟timek循环检测若当前六元状态已标记输出0 00并退出标记状态记录当前农夫和牛的位置及方向移动函数move()计算前方坐标(x dx[f], y dy[f])若前方可通行m[前方] 1更新位置否则f (f 1) % 4顺时针转向农夫和牛独立执行上述逻辑移动后检查是否相遇farmer.x cow.x farmer.y cow.y输出结果相遇时间timek时间/空间复杂度时间复杂度O ( T ) O(T)O(T)T TT为相遇时间或进入循环前的步数上界为状态空间大小10 × 10 × 4 × 10 × 10 × 4 160000 10 \times 10 \times 4 \times 10 \times 10 \times 4 16000010×10×4×10×10×4160000空间复杂度O ( 10 × 10 × 4 × 10 × 10 × 4 ) O(10 \times 10 \times 4 \times 10 \times 10 \times 4)O(10×10×4×10×10×4)六维标记数组状态模拟的核心思想同步移动农夫和牛每分钟同时决策、同时移动移动后检查是否同格方向循环性四个方向用0 ∼ 3 0 \sim 30∼3编码顺时针转为(f 1) % 4状态空间有限性位置最多100 100100种方向4 44种两者组合状态有限必然在有限步内相遇或循环六维数组去重将农夫和牛的完整状态位置方向作为整体标记精确检测循环适用于网格模拟、同步移动、循环检测类问题【算法标签】#普及 #模拟【代码详解】#includebits/stdc.husingnamespacestd;intm[15][15]{0};// 地图数组0 表示障碍1 表示可通行intdx[4]{-1,0,1,0};// 方向数组北、东、南、西 的 x 偏移量intdy[4]{0,1,0,-1};// 方向数组北、东、南、西 的 y 偏移量// 定义 farmer 和 cow 的结构体structshiti{intx;// 当前行坐标inty;// 当前列坐标intf;// 当前方向0 北1 东2 南3 西}cow,farmer;// cow 表示牛farmer 表示农夫// 移动函数模拟农夫和牛的移动voidmove(){// 计算农夫和牛的前方位置intfxfarmer.xdx[farmer.f],fyfarmer.ydy[farmer.f];// 农夫的前方位置intcxcow.xdx[cow.f],cycow.ydy[cow.f];// 牛的前方位置// 农夫移动逻辑if(m[fx][fy]){// 如果农夫前方可通行farmer.xfx;// 更新农夫的位置farmer.yfy;}else{// 如果前方是障碍farmer.f(farmer.f1)%4;// 农夫转向顺时针旋转 90 度}// 牛移动逻辑if(m[cx][cy]){// 如果牛前方可通行cow.xcx;// 更新牛的位置cow.ycy;}else{// 如果前方是障碍cow.f(cow.f1)%4;// 牛转向顺时针旋转 90 度}}intmain(){inttimek0;// 记录时间移动次数chartmpc;// 用于临时读取地图字符boolmark[11][11][4][11][11][4]{0};// 状态标记数组用于记录农夫和牛的位置和方向是否重复// 构建地图for(inti1;i10;i){for(intj1;j10;j){cintmpc;// 读取地图字符if(tmpc*)continue;// 如果是障碍物跳过m[i][j]1;// 标记为可通行if(tmpcC){// 如果是牛cow.xi;// 记录牛的初始位置cow.yj;cow.f0;// 初始方向为北}if(tmpcF){// 如果是农夫farmer.xi;// 记录农夫的初始位置farmer.yj;farmer.f0;// 初始方向为北}}}// 模拟运动while(farmer.x!cow.x||farmer.y!cow.y){// 当农夫和牛不在同一位置时循环timek;// 时间增加if(mark[farmer.x][farmer.y][farmer.f][cow.x][cow.y][cow.f]1){// 如果当前状态已出现过cout0;// 输出 0表示无法相遇return0;}mark[farmer.x][farmer.y][farmer.f][cow.x][cow.y][cow.f]1;// 标记当前状态move();// 农夫和牛移动}// 输出相遇时间couttimek;return0;}【运行结果】*...*..... ......*... ...*...*.. .......... ...*.F.... *.....*... ...*...... ..C......* ...*.*.... .*.*...... 49