本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AtCoderD - Escape from the Ice Rink【题目描述】Takahashi is trapped in a rectangular ice rink withH HHrows andW WWcolumns. There areN NNpillars standing inside the rink. Thei ii-th pillar is located at coordinates( R i , C i ) (R_i, C_i)(Ri,Ci). Here, coordinates( r , c ) (r, c)(r,c)denote the cell in ther rr-th row from the top and thec cc-th column from the left.Takahashi is currently at the top-left corner at coordinates( 1 , 1 ) (1, 1)(1,1)and aims to reach the goal at the bottom-right corner at coordinates( H , W ) (H, W)(H,W).The ice on the rink is extremely slippery, and once he starts sliding, he cannot change direction or stop midway. Inone move, Takahashi chooses one of the four directions — up, down, left, or right — and begins sliding, continuing straight in that direction until one of the following conditions is met:Reaching the edge of the rink:Since he cannot go outside the rink, he stops at the edge cell.Reaching the cell just before a pillar:If the next cell in the sliding direction contains a pillar, he cannot enter the cell with the pillar, so he stops at the cell just before it.Here, up means the direction of decreasing row number, down means increasing row number, left means decreasing column number, and right means increasing column number.If he cannot advance even one cell in the chosen direction (i.e., the adjacent cell contains a pillar, or he is already at the edge of the rink and no cell exists in that direction), Takahashi does not move and stays at his current cell.This still counts as one move.Takahashi may visit the same cell any number of times.Find the minimum number of moves required for Takahashi to start from coordinates( 1 , 1 ) (1, 1)(1,1)andstopat coordinates( H , W ) (H, W)(H,W). Stopping at coordinates( H , W ) (H, W)(H,W)means that, following the movement rules described above, he comes to a stop at coordinates( H , W ) (H, W)(H,W). Simply passing through coordinates( H , W ) (H, W)(H,W)while sliding does not count as reaching the goal.If it is impossible to reach the goal, output-1.It is guaranteed that there are no pillars at coordinates( 1 , 1 ) (1, 1)(1,1)or coordinates( H , W ) (H, W)(H,W).高桥被困在一个H HH行W WW列的矩形滑冰场中。冰场内有N NN个柱子。第i ii个柱子的坐标为( R i , C i ) (R_i, C_i)(Ri,Ci)。这里坐标( r , c ) (r, c)(r,c)表示从上往下数第r rr行、从左往右数第c cc列的单元格。高桥目前位于左上角坐标( 1 , 1 ) (1, 1)(1,1)处目标是到达右下角坐标( H , W ) (H, W)(H,W)处的终点。冰面上的冰非常滑一旦他开始滑动他就不能改变方向或中途停止。在一次移动中高桥选择四个方向之一——上、下、左、右——并开始滑动一直沿该方向直线滑动直到满足以下条件之一到达冰场边缘由于他不能离开冰场他在边缘单元格处停止。到达柱子前一个单元格如果滑动方向的下一个单元格包含柱子他不能进入柱子所在的单元格因此他会在柱子之前的单元格停止。这里上是指行号减少的方向下是指行号增加的方向左是指列号减少的方向右是指列号增加的方向。如果他在所选方向上甚至无法前进一个单元格即相邻单元格包含柱子或者他已经处于冰场边缘且该方向上没有单元格高桥不会移动并停留在当前单元格。这仍然算作一次移动。高桥可以多次访问同一个单元格。求高桥从坐标( 1 , 1 ) (1, 1)(1,1)出发停止在坐标( H , W ) (H, W)(H,W)所需的最少移动次数。停止在坐标( H , W ) (H, W)(H,W)意味着按照上述移动规则他停在了坐标( H , W ) (H, W)(H,W)处。仅仅在滑动过程中经过坐标( H , W ) (H, W)(H,W)不算到达终点。如果无法到达终点输出-1。保证坐标( 1 , 1 ) (1, 1)(1,1)和坐标( H , W ) (H, W)(H,W)处没有柱子。【输入】H HHW WWN NNR 1 R_1R1C 1 C_1C1R 2 R_2R2C 2 C_2C2⋮ \vdots⋮R N R_NRNC N C_NCNThe first line containsH HH, the number of rows of the ice rink,W WW, the number of columns, andN NN, the number of pillars, separated by spaces.The followingN NNlines contain the coordinates of each pillar. IfN 0 N 0N0, this part does not exist.The( 1 i ) (1 i)(1i)-th line (1 ≤ i ≤ N 1 \leq i \leq N1≤i≤N) contains the row numberR i R_iRiand column numberC i C_iCiof thei ii-th pillar, separated by spaces.【输出】Print in one line the minimum number of moves required for Takahashi to stop at coordinates( H , W ) (H, W)(H,W)starting from coordinates( 1 , 1 ) (1, 1)(1,1). If it is impossible, print-1.【输入样例】3 3 1 2 2【输出样例】2【算法标签】#BFS-二维【代码详解】#includebits/stdc.husingnamespacestd;typedefpairint,intPII;// 定义坐标对类型constintN105;// 定义网格最大尺寸inth,w,n;// 网格高度h宽度w障碍物数量nintdist[N][N];// 距离数组存储到每个格子的最短距离intdx[4]{-1,1,0,0};// 四个方向的x偏移上下左右intdy[4]{0,0,-1,1};// 四个方向的y偏移上下左右mapPII,intmp;// 障碍物映射表存储障碍物位置voidbfs()// 广度优先搜索函数{memset(dist,0x3f,sizeof(dist));// 初始化所有距离为无穷大dist[1][1]0;// 起点距离为0queuePIIq;// 广度优先搜索队列q.push({1,1});// 起点入队while(!q.empty())// 当队列不为空时循环{intxq.front().first,yq.front().second;// 取出队首坐标q.pop();// 出队for(inti0;i4;i)// 遍历四个方向{intnxx,nyy;// 初始化滑动终点while(true)// 沿着当前方向滑动{inttxnxdx[i];// 计算下一个位置x坐标inttynydy[i];// 计算下一个位置y坐标if(tx1||txh||ty1||tyw)break;// 超出边界则停止if(mp.count({tx,ty}))break;// 遇到障碍物则停止nxtx,nyty;// 更新滑动位置}if(dist[nx][ny]0x3f3f3f3f)// 如果目标位置未访问过{dist[nx][ny]dist[x][y]1;// 更新距离q.push({nx,ny});// 目标位置入队}}}}intmain()// 主函数{cinhwn;// 输入网格尺寸和障碍物数量for(inti1;in;i)// 读取所有障碍物{intr,c;// 障碍物行坐标r列坐标ccinrc;// 输入障碍物坐标mp[{r,c}]1;// 在障碍物映射表中标记}bfs();// 执行广度优先搜索if(dist[h][w]0x3f3f3f3f)cout-1endl;// 如果终点不可达输出-1elsecoutdist[h][w]endl;// 否则输出最短距离return0;// 程序正常结束}【运行结果】3 3 1 2 2 2
题解：AtCoder AT_awc0083_d Escape from the Ice Rink
本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AtCoderD - Escape from the Ice Rink【题目描述】Takahashi is trapped in a rectangular ice rink withH HHrows andW WWcolumns. There areN NNpillars standing inside the rink. Thei ii-th pillar is located at coordinates( R i , C i ) (R_i, C_i)(Ri,Ci). Here, coordinates( r , c ) (r, c)(r,c)denote the cell in ther rr-th row from the top and thec cc-th column from the left.Takahashi is currently at the top-left corner at coordinates( 1 , 1 ) (1, 1)(1,1)and aims to reach the goal at the bottom-right corner at coordinates( H , W ) (H, W)(H,W).The ice on the rink is extremely slippery, and once he starts sliding, he cannot change direction or stop midway. Inone move, Takahashi chooses one of the four directions — up, down, left, or right — and begins sliding, continuing straight in that direction until one of the following conditions is met:Reaching the edge of the rink:Since he cannot go outside the rink, he stops at the edge cell.Reaching the cell just before a pillar:If the next cell in the sliding direction contains a pillar, he cannot enter the cell with the pillar, so he stops at the cell just before it.Here, up means the direction of decreasing row number, down means increasing row number, left means decreasing column number, and right means increasing column number.If he cannot advance even one cell in the chosen direction (i.e., the adjacent cell contains a pillar, or he is already at the edge of the rink and no cell exists in that direction), Takahashi does not move and stays at his current cell.This still counts as one move.Takahashi may visit the same cell any number of times.Find the minimum number of moves required for Takahashi to start from coordinates( 1 , 1 ) (1, 1)(1,1)andstopat coordinates( H , W ) (H, W)(H,W). Stopping at coordinates( H , W ) (H, W)(H,W)means that, following the movement rules described above, he comes to a stop at coordinates( H , W ) (H, W)(H,W). Simply passing through coordinates( H , W ) (H, W)(H,W)while sliding does not count as reaching the goal.If it is impossible to reach the goal, output-1.It is guaranteed that there are no pillars at coordinates( 1 , 1 ) (1, 1)(1,1)or coordinates( H , W ) (H, W)(H,W).高桥被困在一个H HH行W WW列的矩形滑冰场中。冰场内有N NN个柱子。第i ii个柱子的坐标为( R i , C i ) (R_i, C_i)(Ri,Ci)。这里坐标( r , c ) (r, c)(r,c)表示从上往下数第r rr行、从左往右数第c cc列的单元格。高桥目前位于左上角坐标( 1 , 1 ) (1, 1)(1,1)处目标是到达右下角坐标( H , W ) (H, W)(H,W)处的终点。冰面上的冰非常滑一旦他开始滑动他就不能改变方向或中途停止。在一次移动中高桥选择四个方向之一——上、下、左、右——并开始滑动一直沿该方向直线滑动直到满足以下条件之一到达冰场边缘由于他不能离开冰场他在边缘单元格处停止。到达柱子前一个单元格如果滑动方向的下一个单元格包含柱子他不能进入柱子所在的单元格因此他会在柱子之前的单元格停止。这里上是指行号减少的方向下是指行号增加的方向左是指列号减少的方向右是指列号增加的方向。如果他在所选方向上甚至无法前进一个单元格即相邻单元格包含柱子或者他已经处于冰场边缘且该方向上没有单元格高桥不会移动并停留在当前单元格。这仍然算作一次移动。高桥可以多次访问同一个单元格。求高桥从坐标( 1 , 1 ) (1, 1)(1,1)出发停止在坐标( H , W ) (H, W)(H,W)所需的最少移动次数。停止在坐标( H , W ) (H, W)(H,W)意味着按照上述移动规则他停在了坐标( H , W ) (H, W)(H,W)处。仅仅在滑动过程中经过坐标( H , W ) (H, W)(H,W)不算到达终点。如果无法到达终点输出-1。保证坐标( 1 , 1 ) (1, 1)(1,1)和坐标( H , W ) (H, W)(H,W)处没有柱子。【输入】H HHW WWN NNR 1 R_1R1C 1 C_1C1R 2 R_2R2C 2 C_2C2⋮ \vdots⋮R N R_NRNC N C_NCNThe first line containsH HH, the number of rows of the ice rink,W WW, the number of columns, andN NN, the number of pillars, separated by spaces.The followingN NNlines contain the coordinates of each pillar. IfN 0 N 0N0, this part does not exist.The( 1 i ) (1 i)(1i)-th line (1 ≤ i ≤ N 1 \leq i \leq N1≤i≤N) contains the row numberR i R_iRiand column numberC i C_iCiof thei ii-th pillar, separated by spaces.【输出】Print in one line the minimum number of moves required for Takahashi to stop at coordinates( H , W ) (H, W)(H,W)starting from coordinates( 1 , 1 ) (1, 1)(1,1). If it is impossible, print-1.【输入样例】3 3 1 2 2【输出样例】2【算法标签】#BFS-二维【代码详解】#includebits/stdc.husingnamespacestd;typedefpairint,intPII;// 定义坐标对类型constintN105;// 定义网格最大尺寸inth,w,n;// 网格高度h宽度w障碍物数量nintdist[N][N];// 距离数组存储到每个格子的最短距离intdx[4]{-1,1,0,0};// 四个方向的x偏移上下左右intdy[4]{0,0,-1,1};// 四个方向的y偏移上下左右mapPII,intmp;// 障碍物映射表存储障碍物位置voidbfs()// 广度优先搜索函数{memset(dist,0x3f,sizeof(dist));// 初始化所有距离为无穷大dist[1][1]0;// 起点距离为0queuePIIq;// 广度优先搜索队列q.push({1,1});// 起点入队while(!q.empty())// 当队列不为空时循环{intxq.front().first,yq.front().second;// 取出队首坐标q.pop();// 出队for(inti0;i4;i)// 遍历四个方向{intnxx,nyy;// 初始化滑动终点while(true)// 沿着当前方向滑动{inttxnxdx[i];// 计算下一个位置x坐标inttynydy[i];// 计算下一个位置y坐标if(tx1||txh||ty1||tyw)break;// 超出边界则停止if(mp.count({tx,ty}))break;// 遇到障碍物则停止nxtx,nyty;// 更新滑动位置}if(dist[nx][ny]0x3f3f3f3f)// 如果目标位置未访问过{dist[nx][ny]dist[x][y]1;// 更新距离q.push({nx,ny});// 目标位置入队}}}}intmain()// 主函数{cinhwn;// 输入网格尺寸和障碍物数量for(inti1;in;i)// 读取所有障碍物{intr,c;// 障碍物行坐标r列坐标ccinrc;// 输入障碍物坐标mp[{r,c}]1;// 在障碍物映射表中标记}bfs();// 执行广度优先搜索if(dist[h][w]0x3f3f3f3f)cout-1endl;// 如果终点不可达输出-1elsecoutdist[h][w]endl;// 否则输出最短距离return0;// 程序正常结束}【运行结果】3 3 1 2 2 2
