本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P1849 [USACO12MAR] Tractor S - 洛谷【题目描述】经过一天漫长的工作农场主 John 完全忘记了他的拖拉机还在场地中央。他的奶牛们总喜欢和他搞些恶作剧它们在场地的不同位置丢下n nn堆干草。这样 John 就必须先移走一些干草堆才能将拖拉机开走。拖拉机和干草堆都可以看作是二维平面上的点它们的坐标都是整数没有哪堆干草的坐标和拖拉机的初始坐标一致。John 驾驶拖拉机只能沿着坐标轴的方向移动若干单位长度比如说他可以先朝北移动2 22个单位长度再向东移动3 33个单位长度等等。拖拉机不能移动到干草堆所占据的点。请你帮助 John 计算一下最少要移动多少堆干草才能将拖拉机开回坐标原点。【输入】输入的第一行是三个用空格隔开的整数依次代表干草的堆数n nn和拖拉机的起始坐标( x 0 , y 0 ) (x_0, y_0)(x0​,y0​)。第2 22行到第( n 1 ) (n1)(n1)行每行有两个用空格隔开的整数第( i 1 ) (i 1)(i1)行的整数x i , y i x_i, y_ixi​,yi​代表第i ii堆干草的坐标为( x i , y i ) (x_i, y_i)(xi​,yi​)。【输出】一行一个整数表示最少要移动多少堆干草 John 才能将拖拉机开回坐标原点。【输入样例】7 6 3 6 2 5 2 4 3 2 1 7 3 5 4 6 4【输出样例】1【算法标签】#普及plus【代码详解】#includebits/stdc.husingnamespacestd;typedefpairint,intPII;// 定义坐标对类型constintN1005;// 最大网格尺寸intn;// 输入的火把数量inta[N][N],f[N][N];// a: 标记危险位置f: 从起点到每个点的最短路径长度intdx[4]{-1,1,0,0};// 方向数组上下左右intdy[4]{0,0,-1,1};// 方向数组上下左右/** * 广度优先搜索计算最短路径 * param x 起始点x坐标 * param y 起始点y坐标 */voidbfs(intx,inty){memset(f,0x3f,sizeof(f));// 初始化距离为无穷大f[x][y]0;// 起点距离为0queuePIIq;// 定义队列q.push({x,y});// 将起点加入队列while(!q.empty())// 当队列不为空时{intxxq.front().first,yyq.front().second;// 取出队头坐标q.pop();// 弹出队头for(inti0;i4;i)// 遍历四个方向{intnxxxdx[i],nyyydy[i];// 计算相邻位置if(nx0||nx1001||ny0||ny1001)// 越界检查continue;// 如果通过当前点到达相邻点距离更短if(f[nx][ny]f[xx][yy]a[nx][ny]){f[nx][ny]f[xx][yy]a[nx][ny];// 更新最短距离q.push({nx,ny});// 将新位置加入队列}// 调试输出// cout nx ny a[nx][ny] nx ny a[nx][ny] endl;// cout f[] f[nx][ny] endl;}}}intmain(){cinn;// 输入火把数量intx0,y0;cinx0y0;// 输入起始坐标// 标记火把位置for(inti1;in;i){intx,y;cinxy;// 输入火把坐标a[x][y]1;// 标记该位置为危险位置}bfs(x0,y0);// 计算从起点到所有位置的最短路径// 调试输出// for (int i0; i8; i)// {// for (int j0; j8; j)// cout f[i][j] ;// cout endl;// }coutf[0][0]endl;// 输出到达(0,0)的最短路径长度return0;}【运行结果】7 6 3 6 2 5 2 4 3 2 1 7 3 5 4 6 4 1