题目背景
《爱与愁的故事第三弹·shopping》最终章。
题目描述
爱与愁大神买完东西后，打算坐车离开中山路。现在爱与愁大神在 x1,y1 处，车站在 x2,y2 处。现在给出一个 n×n(n≤1000) 的地图，0 表示马路，1 表示店铺（不能从店铺穿过），爱与愁大神只能垂直或水平着在马路上行进。爱与愁大神为了节省时间，他要求最短到达目的地距离（每两个相邻坐标间距离为 1）。你能帮他解决吗？
输入格式
第 1 行包含一个数 n。
第 2 行到第 n+1 行：整个地图描述（0 表示马路，1 表示店铺，注意两个数之间没有空格）。
第 n+2 行：四个数 x1,y1,x2,y2。
输出格式
只有 1 行，即最短到达目的地距离。
输入输出样例
输入 #1复制
3 001 101 100 1 1 3 3
输出 #1复制
4
说明/提示
对于 20% 数据，满足 1≤n≤100。
对于 100% 数据，满足 1≤n≤1000。
题目链接：P1746 离开中山路 - 洛谷
学习链接：BFS习题课(上) | 从此搞懂搜索题的套路! | 入门必看_哔哩哔哩_bilibili
代码如下：
#include<bits/stdc++.h>
using namespace std;
int n;//矩阵规模
//定义pair
typedef pair<int,int> PII;
queue<PII> q;
char g[1005][1005];//地图
int dist[1005][1005];//距离数组
int x[4]={-1,0,1,0};
int y[4]={0,1,0,-1};int bfs(int x1,int y1,int x2,int y2)
{//初始化memset(dist,-1,sizeof(dist)); //入队q.push({x1,y1});dist[x1][y1]=0;//若队列不为空while(!q.empty()) {//取出队头auto t=q.front();//出队q.pop();//将其符合条件的方向坐标入队for(int i=0;i<4;i++){//下一个试探的坐标 int nx=t.first+x[i];int ny=t.second+y[i];//越界跳过if(nx<1 || nx>n || ny<1 || ny>n) continue;//不是马路也跳过if(g[nx][ny]!='0') continue;//标记过距离的也跳过if(dist[nx][ny]>=0) continue;//符合条件的//入队q.push({nx,ny});//计算距离dist[nx][ny]=dist[t.first][t.second]+1;//到达目的地，输出if(nx == x2 && ny == y2) return dist[nx][ny]; } }
}
int main()
{cin>>n;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>g[i][j];int a,b,c,d;cin>>a>>b>>c>>d;cout<<bfs(a,b,c,d)<<endl;return 0;
}
