本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。
欢迎大家订阅我的专栏：算法题解：C++与Python实现！
附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总
【题目来源】
洛谷：P5195 [USACO05DEC] Knights of Ni S - 洛谷
【题目描述】
贝茜遇到了一件很麻烦的事：她无意中闯入了森林里的一座城堡，如果她想回家，就必须穿过这片由骑士们守护着的森林。为了能安全地离开，贝茜不得不按照骑士们的要求，在森林寻找一种特殊的灌木并带一棵给他们。
当然，贝茜想早点离开这可怕的森林，于是她必须尽快完成骑士们给的任务，贝茜随身带着这片森林的地图，地图上的森林被放入了直角坐标系，并按x , y x,yx,y轴上的单位长度划分成了W × H ( 1 ≤ W , H ≤ 1000 ) W \times H\ ( 1 \leq W,H \leq 1000 )W×H(1≤W,H≤1000)块，贝茜在地图上查出了她自己以及骑士们所在的位置，当然地图上也标注了她所需要的灌木生长的区域。某些区域是不能通过的（比如说沼泽地，悬崖，以及食人兔的聚居地）。在没有找到灌木之前，贝茜不能通过骑士们所在的那个区域，为了确保她自己不会迷路，贝茜只向正北、正东、正南、正西四个方向移动（注意，她不会走对角线）。她要走整整一天，才能从某块区域走到与它相邻的那块区域。
贝茜希望你能帮她计算一下，她最少需要多少天才可脱离这可怕的地方？输入数据保证贝茜一定能完成骑士的任务。
【输入】
第一行输入2 22个用空格隔开的整数，即题目中提到的W , H W,HW,H。
接下来输入贝茜持有的地图，每一行用若干个数字代表地图上对应行的地形。第一行描述了地图最北的那一排土地；最后一行描述的则是最南面的。相邻的数字所对应的区域是相邻的。如果地图的宽小于或等于40 4040，那每一行数字恰好对应了地图上的一排土地。如果地图的宽大于40 4040，那每行只会给出40 4040个数字，并且保证除了最后一行的每一行都包含恰好40 4040个数字。没有哪一行描述的区域分布在两个不同的行里。
地图上的数字所对应的地形：
- 0 00：贝茜可以通过的空地；
- 1 11：由于各种原因而不可通行的区域；
- 2 22：贝茜现在所在的位置；
- 3 33：骑士们的位置；
- 4 44：长着贝茜需要的灌木的土地。
【输出】
输出一个正整数，即贝茜最少要花多少天才能完成骑士们给的任务。
【输入样例】
8 4 4 1 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 2 1 1 3 0 4 0 0 0 0 4 1 1 1 0【输出样例】
11【算法标签】
#普及plus #BFS-二维
【代码详解】
#include<bits/stdc++.h>usingnamespacestd;constintN=1005;// 定义网格最大尺寸inth,w,ans=1e9;// 网格高度h，宽度w，答案ans（初始化为极大值）inta[N][N],dist1[N][N],dist2[N][N];// 网格数组a，起点距离dist1，钥匙距离dist2structNode{intr,c;// 结构体存储坐标}st,ks[N*N],fs[N*N];// 起点st，钥匙数组ks，食物数组fsintcur1,cur2;// 钥匙数量cur1，食物数量cur2boolvis[N][N];// 访问标记数组intdx[4]={-1,1,0,0};// 四个方向的x偏移intdy[4]={0,0,-1,1};// 四个方向的y偏移voidbfs1()// 从起点开始的第一轮广度优先搜索{memset(vis,0,sizeof(vis));// 初始化访问标记为未访问memset(dist1,0x3f,sizeof(dist1));// 初始化起点距离为无穷大queue<Node>q;// 广度优先搜索队列q.push(st);// 起点入队dist1[st.r][st.c]=0;// 起点到自己的距离为0vis[st.r][st.c]=1;// 标记起点为已访问while(!q.empty())// 当队列不为空时循环{intx=q.front().r,y=q.front().c;// 取出队首坐标q.pop();// 出队for(inti=0;i<4;i++)// 遍历四个方向{intnx=x+dx[i],ny=y+dy[i];// 计算相邻位置if(nx<1||nx>h||ny<1||ny>w||vis[nx][ny]||a[nx][ny]==1||a[nx][ny]==3)continue;// 检查是否越界、已访问、是墙或是钥匙dist1[nx][ny]=dist1[x][y]+1;// 更新相邻位置的距离vis[nx][ny]=1;// 标记相邻位置为已访问q.push({nx,ny});// 相邻位置入队}}}voidbfs2()// 从所有钥匙开始的第二轮广度优先搜索{memset(vis,0,sizeof(vis));// 初始化访问标记为未访问memset(dist2,0x3f,sizeof(dist2));// 初始化钥匙距离为无穷大queue<Node>q;// 广度优先搜索队列for(inti=1;i<=cur1;i++)// 将所有钥匙加入队列{q.push(ks[i]);// 钥匙入队vis[ks[i].r][ks[i].c]=1;// 标记钥匙位置为已访问dist2[ks[i].r][ks[i].c]=0;// 钥匙到自己的距离为0}while(!q.empty())// 当队列不为空时循环{intx=q.front().r,y=q.front().c;// 取出队首坐标q.pop();// 出队for(inti=0;i<4;i++)// 遍历四个方向{intnx=x+dx[i],ny=y+dy[i];// 计算相邻位置if(nx<1||nx>h||ny<1||ny>w||vis[nx][ny]||a[nx][ny]==1)continue;// 检查是否越界、已访问、是墙dist2[nx][ny]=dist2[x][y]+1;// 更新相邻位置的距离vis[nx][ny]=1;// 标记相邻位置为已访问q.push({nx,ny});// 相邻位置入队}}}intmain()// 主函数{cin>>w>>h;// 输入网格宽度w和高度hfor(inti=1;i<=h;i++)// 遍历网格的每一行{for(intj=1;j<=w;j++)// 遍历网格的每一列{cin>>a[i][j];// 输入网格单元格的值if(a[i][j]==2)// 如果当前单元格是起点{st={i,j};// 记录起点坐标}if(a[i][j]==3)// 如果当前单元格是钥匙{ks[++cur1]={i,j};// 记录钥匙坐标，钥匙数量加1}if(a[i][j]==4)// 如果当前单元格是食物{fs[++cur2]={i,j};// 记录食物坐标，食物数量加1}}}bfs1();// 执行从起点开始的广度优先搜索bfs2();// 执行从所有钥匙开始的广度优先搜索for(inti=1;i<=cur2;i++)// 遍历所有食物位置{Node t=fs[i];// 获取当前食物的坐标ans=min(ans,dist1[t.r][t.c]+dist2[t.r][t.c]);// 更新最短路径长度为起点到食物距离加上钥匙到食物距离的最小值}cout<<ans<<endl;// 输出最短路径长度return0;// 程序正常结束}【运行结果】
8 4 4 1 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 2 1 1 3 0 4 0 0 0 0 4 1 1 1 0 11
