企业官网建设流程全解析

本文分享的必刷题目是从蓝桥云课、洛谷、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

【核心思想】

1. 问题分析：给定10 × 10 10 \times 1010×10网格地图，农夫F和两头牛C初始方向均为正北。每分钟两者同时移动：若前方可通行则前进一格，否则顺时针转90 ∘ 90^\circ90∘。求两者相遇所需的最少分钟数，若永远不会相遇则输出0 00。这是一个状态模拟 + 循环检测问题。

2. 算法选择：

   • 逐分钟模拟：按照规则同时移动农夫和牛，每分钟更新一次位置
   • 六维状态标记：用mark[fx][fy][ff][cx][cy][cf]记录状态（位置+方向），若状态重复则说明进入循环，永远无法相遇

3. 关键步骤：

   • 读入地图：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

4. 时间/空间复杂度：

   • 时间复杂度：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×4=160000
   • 空间复杂度：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)，六维标记数组

5. 状态模拟的核心思想：

   • 同步移动：农夫和牛每分钟同时决策、同时移动，移动后检查是否同格
   • 方向循环性：四个方向用0 ∼ 3 0 \sim 30∼3编码，顺时针转为(f + 1) % 4
   • 状态空间有限性：位置最多100 100100种，方向4 44种，两者组合状态有限，必然在有限步内相遇或循环
   • 六维数组去重：将农夫和牛的完整状态（位置+方向）作为整体标记，精确检测循环
   • 适用于网格模拟、同步移动、循环检测类问题

【算法标签】

#普及 #模拟

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;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(){// 计算农夫和牛的前方位置intfx=farmer.x+dx[farmer.f],fy=farmer.y+dy[farmer.f];// 农夫的前方位置intcx=cow.x+dx[cow.f],cy=cow.y+dy[cow.f];// 牛的前方位置// 农夫移动逻辑if(m[fx][fy]){// 如果农夫前方可通行farmer.x=fx;// 更新农夫的位置farmer.y=fy;}else{// 如果前方是障碍farmer.f=(farmer.f+1)%4;// 农夫转向（顺时针旋转 90 度）}// 牛移动逻辑if(m[cx][cy]){// 如果牛前方可通行cow.x=cx;// 更新牛的位置cow.y=cy;}else{// 如果前方是障碍cow.f=(cow.f+1)%4;// 牛转向（顺时针旋转 90 度）}}intmain(){inttimek=0;// 记录时间（移动次数）chartmpc;// 用于临时读取地图字符boolmark[11][11][4][11][11][4]={0};// 状态标记数组，用于记录农夫和牛的位置和方向是否重复// 构建地图for(inti=1;i<=10;i++){for(intj=1;j<=10;j++){cin>>tmpc;// 读取地图字符if(tmpc=='*')continue;// 如果是障碍物，跳过m[i][j]=1;// 标记为可通行if(tmpc=='C'){// 如果是牛cow.x=i;// 记录牛的初始位置cow.y=j;cow.f=0;// 初始方向为北}if(tmpc=='F'){// 如果是农夫farmer.x=i;// 记录农夫的初始位置farmer.y=j;farmer.f=0;// 初始方向为北}}}// 模拟运动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){// 如果当前状态已出现过cout<<0;// 输出 0（表示无法相遇）return0;}mark[farmer.x][farmer.y][farmer.f][cow.x][cow.y][cow.f]=1;// 标记当前状态move();// 农夫和牛移动}// 输出相遇时间cout<<timek;return0;}

【运行结果】

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