本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AtCoderE - Warehouse Robot Delivery【题目描述】Takahashi is a programmer for delivery robots working in a large warehouse.高桥是在一个大型仓库工作的送货机器人程序员。The warehouse floor is divided into anN × N N \times NN×Ngrid. The cell in ther rr-th row from the top( 1 ≤ r ≤ N ) (1 \leq r \leq N)(1≤r≤N)and thec cc-th column from the left( 1 ≤ c ≤ N ) (1 \leq c \leq N)(1≤c≤N)is assigned the number( r − 1 ) × N c (r-1) \times N c(r−1)×Nc. That is, the cells are numbered1 , 2 , … , N 1, 2, \ldots, N1,2,…,Nfrom left to right in row1 11, thenN 1 , N 2 , … , 2 N N1, N2, \ldots, 2NN1,N2,…,2Nfrom left to right in row2 22, and so on. There are no walls or obstacles on the grid, and all cells are passable.仓库地面被划分成一个N × N N × NN×N的网格。从上往下第r rr行1 ≤ r ≤ N 1 ≤ r ≤ N1≤r≤N和从左往右第c cc列1 ≤ c ≤ N 1 ≤ c ≤ N1≤c≤N的单元格被赋予编号( r − 1 ) × N c (r-1) × N c(r−1)×Nc。也就是说单元格的编号方式为在第1 11行中从左到右编号1 , 2 , … , N 1, 2, …, N1,2,…,N然后在第 2 行中从左到右编号N 1 , N 2 , … , 2 N N1, N2, …, 2NN1,N2,…,2N依此类推。网格上没有墙壁或障碍物所有单元格均可通行。The delivery robot is currently waiting at cellS SS. Takahashi needs to move the robot to the shipping area at cellT TT.S SSandT TTare different cells. In one move, the robot can move one cell to an adjacent cell in one of the four directions (up, down, left, right). However, the robot cannot move outside the grid.送货机器人当前在单元格S SS处等待。高桥需要将机器人移动到位于单元格T TT的发货区。S SS和T TT是不同的单元格。在单次移动中机器人可以向四个方向上、下、左、右之一移动到相邻的单元格。但机器人不能移动到网格外。During its movement, the robot must collect packages fromM MMdesignated shelves. The cell numbersP 1 , P 2 , … , P M P_1, P_2, \ldots, P_MP1​,P2​,…,PM​where the shelves with packages to collect are located are given. TheseM MMcells may be visited in any order, but all of them must be visited at least once before reaching cellT TT. Note that passing through the same cell multiple times during movement is allowed.在移动过程中机器人必须从M MM个指定的货架上收取包裹。给出了存放待收取包裹的货架所在的单元格编号P 1 , P 2 , … , P M P_1, P_2, …, P_MP1​,P2​,…,PM​。这M MM个单元格可以以任意顺序访问但在到达单元格T TT之前所有单元格都必须至少访问一次。注意允许在移动过程中多次经过同一个单元格。Find the minimum number of moves required for the robot to start from cellS SS, visit allM MMdesignated cells, and reach cellT TT. Here, the number of moves refers to the total number of times the robot moves to an adjacent cell.求机器人从单元格S SS出发访问所有M MM个指定单元格并到达单元格T TT所需的最少移动次数。此处移动次数指机器人移动到相邻单元格的总次数。【输入】N NNM MMS SST TTP 1 P_1P1​P 2 P_2P2​⋯ \cdots⋯P M P_MPM​The first line contains an integerN NNrepresenting the side length of the grid and an integerM MMrepresenting the number of cells to visit, separated by a space.The second line contains an integerS SSrepresenting the starting cell number and an integerT TTrepresenting the destination cell number, separated by a space.The third line contains integersP 1 , P 2 , … , P M P_1, P_2, \ldots, P_MP1​,P2​,…,PM​representing the cell numbers to visit, separated by spaces. IfM 0 M 0M0, the third line is not given.【输出】Print in one line the minimum number of moves required for the robot to start from cellS SS, visit all designated cells, and reach cellT TT.【输入样例】3 2 1 9 5 3【输出样例】6【解题思路】【算法标签】#状压DP#【代码详解】#includebits/stdc.husingnamespacestd;constintN20,INF1e9;#defineintlonglongtypedefpairint,intPII;intn,m,s,t;// n: 网格大小m: 中间点数s: 起点t: 终点PII p[N];// 存储所有点(包括起点、中间点、终点)的坐标intdp[1N][N];// dp[mask][u]: 访问过mask中的点当前在点u的最小距离intdist[N][N];// 点之间的距离// 将编号t(1~n*n)转换为网格坐标(x, y)1-basedPIIgetpos(intt){intx(tn-1)/n;// 行号intyt%n;// 列号if(y0)// 如果列号为0表示是最后一列{yn;}return{x,y};}// 计算点x和点y之间的曼哈顿距离intgetdist(intx,inty){returnabs(p[x].first-p[y].first)abs(p[x].second-p[y].second);}signedmain(){cinnmst;// 读入网格大小、中间点数、起点、终点p[0]getpos(s);// 起点是第0个点for(inti1;im;i)// 读入中间点{intx;cinx;p[i]getpos(x);}p[m]getpos(t);// 终点是第m个点// 计算所有点对之间的距离for(inti0;im;i){for(intj0;jm;j){dist[i][j]getdist(i,j);}}memset(dp,0x3f,sizeof(dp));// 初始化DP数组为极大值dp[0][0]0;// 初始状态从起点(点0)开始// 状态压缩DPfor(intmask0;mask(1m);mask)// 遍历所有状态掩码{for(intu0;um;u)// 遍历当前所在点{if(dp[mask][u]0x3f3f3f3f)// 当前状态不可达{continue;}for(intv1;vm;v)// 尝试前往下一个点v{if(mask(1(v-1)))// 如果点v已经被访问过{continue;}intnew_maskmask|(1(v-1));// 新状态掩码intnew_valuedp[mask][u]dist[u][v];// 新距离if(new_valuedp[new_mask][v])// 如果新距离更小{dp[new_mask][v]new_value;// 更新DP值}}}}intansINF;for(inti0;im;i)// 遍历所有点作为访问完所有中间点后的位置{// dp[(1m)-1][i]: 访问完所有m个中间点当前在点i的最小距离// dist[i][m]: 从点i到终点的距离ansmin(ans,dp[(1m)-1][i]dist[i][m]);}coutansendl;// 输出最短总距离return0;}【运行结果】3 2 1 9 5 3 6