算法竞赛备考冲刺必刷题（C++） | 洛谷 P1746 离开中山路

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

洛谷：P1746 离开中山路 - 洛谷 (luogu.com.cn)

【题目描述】

爱与愁大神买完东西后，打算坐车离开中山路。现在爱与愁大神在x 1 , y 1 x_1,y_1x1​,y1​处，车站在x 2 , y 2 x_2,y_2x2​,y2​处。现在给出一个n × n ( n ≤ 1000 ) n \times n(n \le 1000)n×n(n≤1000)的地图，0 00表示马路，1 11表示店铺（不能从店铺穿过），爱与愁大神只能垂直或水平着在马路上行进。爱与愁大神为了节省时间，他要求最短到达目的地距离（每两个相邻坐标间距离为1 11）。你能帮他解决吗？

【输入】

第1 11行包含一个数n nn。

第2 22行到第n + 1 n+1n+1行：整个地图描述（0 00表示马路，1 11表示店铺，注意两个数之间没有空格）。

第n + 2 n+2n+2行：四个数x 1 , y 1 , x 2 , y 2 x_1,y_1,x_2,y_2x1​,y1​,x2​,y2​。

【输出】

只有1 11行，即最短到达目的地距离。

【输入样例】

3 001 101 100 1 1 3 3

【输出样例】

4

【算法标签】

《洛谷 P1746 离开中山路》 #模拟# #搜索# #广度优先搜索BFS# #队列#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=1005;// 定义最大网格大小structNode{intx,y,s;// 坐标(x,y)和步数s};intn,a[N][N],x_1,y_1,x_2,y_2,vis[N][N];// 网格大小n，地图a，起点终点坐标，访问标记intdx[4]={-1,1,0,0},dy[4]={0,0,-1,1};// 上下左右四个方向voidbfs(){queue<Node>q;// BFS队列q.push({x_1,y_1,0});// 起点入队vis[x_1][y_1]=1;// 标记起点已访问while(q.size())// 队列不为空时循环{Node t=q.front();// 取队首q.pop();// 出队if(t.x==x_2&&t.y==y_2)// 到达终点{cout<<t.s;// 输出步数return;}for(inti=0;i<4;i++)// 遍历四个方向{intnx=t.x+dx[i],ny=t.y+dy[i];// 计算下一个位置// 边界检查、访问检查、障碍检查if(nx<1||nx>n||ny<1||ny>n||vis[nx][ny]==1||a[nx][ny]!=0)continue;vis[nx][ny]=1;// 标记已访问q.push({nx,ny,t.s+1});// 新位置入队，步数+1}}}intmain(){cin>>n;// 输入网格大小for(inti=1;i<=n;i++)for(intj=1;j<=n;j++)scanf("%1d",&a[i][j]);// 按字符读入数字，避免空格问题cin>>x_1>>y_1>>x_2>>y_2;// 输入起点终点坐标bfs();// 执行BFS搜索return0;}

【运行结果】

3 001 101 100 1 1 3 3 4