题目背景 《爱与愁的故事第三弹·shopping》最终章。
题目描述 爱与愁大神买完东西后，打算坐车离开中山路。
现在爱与愁大神在 (x1, y1) 处，车站在 (x2, y2) 处。
现在给出一个 n × n 的地图，0 表示马路，1 表示店铺（不能从店铺穿过），爱与愁大神只能垂直或水平着在马路上行进。
爱与愁大神为了节省时间，他要求最短到达目的地距离（a[i][j]距离为1），你能帮他解决吗？
输入格式 第 1 行：一个数 n 第 2 行 ~ 第 n+1 行：整个地图描述（0表示马路，1表示店铺，注意两个数之间没有空格） 第 n+2 行：四个数 x1, y1, x2, y2
输出格式 只有 1 行：最短到达目的地距离
输入样例 3 001 101 100 1 1 3 3
输出样例 4
数据范围 对于 20% 数据：n ≤ 100 对于 100% 数据：n ≤ 1000
题解 BFS：
#include <iostream> #include <cstring> #include <cstdio> #include <queue> #define x first #define y second using namespace std; typedef pair<int, int > PII; const int N = 1010; char g[N][N]; int dist[N][N]; int n, x1, y1, x2, y2; int dx[4] = {-1, 0, 1, 0}; int dy[4] = {0, 1, 0, -1}; int bfs() { queue<PII> q; q.push(make_pair(x1, y1)); dist[x1][y1] = 0; while(q.size()) { PII t = q.front(); q.pop(); if(t.x == x2 && t.y == y2) return dist[x2][y2]; for (int i = 0; i < 4; i ++) { int a = t.x + dx[i], b = t.y + dy[i]; if(a < 1 || a > n || b < 1 || b > n || dist[a][b] != -1) continue; if(g[a][b] == '1') continue; q.push(make_pair(a, b)); dist[a][b] = dist[t.x][t.y] + 1; } } } int main() { cin >> n; for (int i = 1; i <= n; i ++) for (int j = 1; j <= n; j ++) cin >> g[i][j]; cin >> x1 >> y1 >> x2 >> y2; memset(dist, -1, sizeof dist); cout << bfs() << endl; return 0; }