本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P2226 [HNOI2001] 遥控赛车比赛【题目描述】全国遥控赛车大赛近日在星沙举行。竞赛选用一块大小为N × M N\times MN×M的场地作为竞赛场地要求选手的赛车在最短的时间内从起点移动到终点。虽然赛场地形高低有少许的起伏但并不存在无法到达的地点。但是在赛场上增加了许多无法穿越的障碍物若赛车在到达终点前撞上障碍物就视为任务失败。在赛车的马力和灵活性等性能相差较小的情况下要控制速度极快的赛车绕开障碍物移动到终点关键是提高选手的反应灵敏度即两次改变赛车运动方向所间隔的最短时间也可称为选手的反应时间。使自己能够更快地控制赛车改变前进的方向。当然由于选手反应灵敏度的不同可选择的路径就会大不相同。如图1 11和图2 22所示对于同一个赛场两位选手的反应时间分别为2 22秒和1 11秒而其到达终点所需的时间分别为18 1818秒和16 1616秒赛车每秒可沿当前方向移动一格从起点出发时算改变一次方向。由图1 11和图2 22可知赛车的最短路线长度是由选手的反应灵敏度所决定的当选手的反应很慢时可能就不会存在可行的路径。你的任务是在能够完成赛程即存在从起点到终点的路径的条件下求出选手每个可能的反应时间所对应的最短路线长度。【输入】第一行包含两个整数N NN和M MM表示赛场的行数和列数。1 ≤ N , M ≤ 100 1≤N, M≤1001≤N,M≤100。第二行有四个整数x 1 x1x1、y 1 y1y1、x 2 x2x2、y 2 y2y2表示赛程的起点和终点的位置分别为( x 1 , y 1 ) (x1, y1)(x1,y1)和( x 2 , y 2 ) (x2,y2)(x2,y2)。接下来N NN行是一个N × M N×MN×M的 0-1 矩阵矩阵中第i ii行第j jj列元素A i , j 1 A_{i,j}1Ai,j​1表示赛场中位置( i , j ) (i,j)(i,j)为赛道A i , j 0 A_{i,j}0Ai,j​0表示赛场中位置( i , j ) (i,j)(i,j)有障碍物。【输出】输出文件可能有多行其中每行输出一个可能的选手反应时间及该时间所对应的最短路线长度。输出文件中必须包含所有符合题目要求的选手反应时间。注意由于选手的反应时间不可能很慢因而不必考虑选手反应时间大于10 1010秒的情况只需输出10 1010以内包含10 1010的解。【输入样例】10 10 1 4 10 7 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 1 1 1 0 1 1 1 1 0 1 0 0 0 0 0 0 0 1 0 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 0 0 0【输出样例】1 16 2 18【核心思想】问题分析给定N × M N \times MN×M的网格地图赛车每秒移动一格从起点( s x , s y ) (sx, sy)(sx,sy)出发到终点( e x , e y ) (ex, ey)(ex,ey)。选手反应时间t tt定义为两次改变方向之间的最小间隔即连续直走至少t tt格后才能转弯。求每个可行反应时间t ∈ [ 1 , 10 ] t \in [1, 10]t∈[1,10]对应的最短路线长度。这是一个分层图最短路问题关键在于状态需记录当前位置和连续直走长度以约束转弯条件。算法选择SPFA 状态扩展将连续直走长度纳入状态维度构建分层图后用 SPFA 求最短路枚举反应时间对每个t tt从1 11到10 1010分别运行最短路若某t tt不可达则更大t tt也不可达提前终止关键步骤初始化读取N , M N, MN,M、起点( s x , s y ) (sx, sy)(sx,sy)、终点( e x , e y ) (ex, ey)(ex,ey)、赛道地图g [ N ] [ M ] g[N][M]g[N][M]枚举反应时间t tt从1 11到10 1010状态定义d i s t [ x ] [ y ] [ d i r ] [ l e n ] dist[x][y][dir][len]dist[x][y][dir][len]表示到达( x , y ) (x, y)(x,y)方向为d i r dirdir0 00上/1 11下/2 22左/3 33右当前已连续直走l e n lenlen格的最短距离初始化d i s t distdist全设为∞ \infty∞从起点向四个方向走第一步算第一次改变方向d i s t [ n x ] [ n y ] [ i ] [ 1 ] 1 dist[nx][ny][i][1] 1dist[nx][ny][i][1]1SPFA 松弛取出队首状态( x , y , k , l ) (x, y, k, l)(x,y,k,l)向四个方向扩展( n x , n y ) (nx, ny)(nx,ny)检查边界和障碍物继续直走i k i kikn l min ⁡ ( 10 , l 1 ) nl \min(10, l1)nlmin(10,l1)更新d i s t [ n x ] [ n y ] [ k ] [ n l ] dist[nx][ny][k][nl]dist[nx][ny][k][nl]转弯i ≠ k i \neq kik仅当l ≥ t l \geq tl≥t时允许n l 1 , n k i nl 1, nk inl1,nki更新d i s t [ n x ] [ n y ] [ n k ] [ n l ] dist[nx][ny][nk][nl]dist[nx][ny][nk][nl]统计答案a n s min ⁡ d i r , l e n d i s t [ e x ] [ e y ] [ d i r ] [ l e n ] ans \min_{dir, len} dist[ex][ey][dir][len]ansmindir,len​dist[ex][ey][dir][len]若a n s ∞ ans \inftyans∞则终止枚举否则输出t tt和a n s ansans时间/空间复杂度时间复杂度O ( 10 × N × M × 4 × 10 × 4 ) O(10 \times N \times M \times 4 \times 10 \times 4)O(10×N×M×4×10×4)枚举10 1010个t tt值每个 SPFA 状态数约N × M × 4 × 10 N \times M \times 4 \times 10N×M×4×10空间复杂度O ( N × M × 4 × 10 ) O(N \times M \times 4 \times 10)O(N×M×4×10)四维距离数组分层图最短路的核心思想状态升维将题目约束连续直走长度作为状态的一维使原本无法直接建模的转弯限制转化为状态转移条件转弯约束转化l ≥ t l \geq tl≥t时才允许改变方向将反应时间约束融入状态转移而非修改图结构连续直走上限l e n lenlen上限设为10 1010因只需考虑t ≤ 10 t \leq 10t≤10避免状态无限膨胀起点特殊处理从起点出发向四个方向的第一步均视为第一次改变方向统一状态初始化适用于带有过程约束如转弯间隔、加速限制、连续操作次数限制的最短路径问题【算法标签】#普及 #SPFA【代码详解】#includebits/stdc.husingnamespacestd;constintN105;// 最大网格尺寸intn,m,ans;// n:行数, m:列数, ans:当前反应时间下的最短路线长度intsx,sy,ex,ey;// 起点和终点坐标intg[N][N];// 赛道地图1表示赛道0表示障碍物// dist[x][y][dir][len]:到达(x,y)时方向为dir当前直走长度为len的最短距离// dir: 0上/1下/2左/3右, len: 当前连续直走的步数限制在10以内intdist[N][N][4][15];intdx[4]{-1,1,0,0};// 四个方向的行偏移intdy[4]{0,0,-1,1};// 四个方向的列偏移structNode{inti,j,k,l;// i:行, j:列, k:方向, l:当前直走长度};voidspfa(intt)// t:当前测试的选手反应时间{queueNodeq;// SPFA队列ans0x3f3f3f3f;// 初始化为无穷大memset(dist,0x3f,sizeof(dist));// 距离数组初始化为无穷大// 从起点出发向四个方向走第一步算第一次改变方向for(inti0;i4;i){intnxsxdx[i];intnysydy[i];if(nx1||nxn||ny1||nym)continue;// 边界检查if(!g[nx][ny])continue;// 障碍物检查dist[nx][ny][i][1]1;// 第一步距离为1直走长度为1q.push({nx,ny,i,1});// 入队}while(!q.empty()){autotmpq.front();q.pop();// 取出队首状态intxtmp.i,ytmp.j,ktmp.k,ltmp.l;// 当前位置和状态for(inti0;i4;i)// 尝试向四个方向扩展{intnxxdx[i];intnyydy[i];if(nx1||nxn||ny1||nym)continue;// 边界检查if(!g[nx][ny])continue;// 障碍物检查if(ki)// 继续直走方向不变{intnlmin(10,l1);// 直走长度加1但不超过10// 松弛如果新距离更短则更新if(dist[nx][ny][k][nl]dist[x][y][k][l]1){dist[nx][ny][k][nl]dist[x][y][k][l]1;q.push({nx,ny,k,nl});}}else// 尝试拐弯改变方向{// 只有当前直走长度l大于等于反应时间t时才能拐弯if(lt)continue;intnl1;// 拐弯后新的直走长度重置为1intnki;// 新的方向// 松弛操作if(dist[nx][ny][nk][nl]dist[x][y][k][l]1){dist[nx][ny][nk][nl]dist[x][y][tmp.k][tmp.l]1;q.push({nx,ny,nk,nl});}}}}// 在所有到达终点的状态中取最短距离for(inti0;i4;i)for(intj0;j10;j)ansmin(ans,dist[ex][ey][i][j]);}intmain(){cinnm;// 读入网格尺寸cinsxsyexey;// 读入起点和终点坐标for(inti1;in;i)// 读入赛道地图for(intj1;jm;j)cing[i][j];// 枚举所有可能的反应时间1到10秒for(intt1;t10;t){spfa(t);// 对当前反应时间运行最短路算法if(ans0x3f3f3f3f)// 如果终点不可达说明更大的反应时间也不可行break;elsecoutt ansendl;// 输出反应时间和对应的最短路线长度}return0;}【运行结果】10 10 1 4 10 7 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 1 1 1 0 1 1 1 1 0 1 0 0 0 0 0 0 0 1 0 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 0 0 0 1 16 2 18