洛谷P1746 离开中山路

题目背景

《爱与愁的故事第三弹·shopping》最终章。

题目描述

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

输入格式

第 $1$ 行包含一个数 $n$。

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

第 $n+2$ 行：四个数 $x_1,y_1,x_2,y_2$。

输出格式

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

样例 #1

样例输入 #1

3
001
101
100
1 1 3 3

样例输出 #1

4

提示

对于 $20\%$ 数据，满足 $1\leq n \le 100$。

对于 $100\%$ 数据，满足 $1\leq n \le 1000$。

题解

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1024;
int n, qx, qy, fx, fy, h, t, a[maxn][maxn], b[maxn][maxn];

struct node {
	int x, y, s;
} q[maxn * maxn];

int mx[4] = {-1, 1, 0, 0}, my[4] = {0, 0, 1, -1};
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			scanf("%1d", &a[i][j]);
	cin >> qx >> qy >> fx >> fy;
	q[t].x = qx, q[t].y = qy, q[t].s = 0, t++;
	b[qx][qy] = 1;
	while (h < t) {
		int x = q[h].x, y = q[h].y, s = q[h].s;
		for (int i = 0; i < 4; i++) {
			int nx = x + mx[i], ny = y + my[i];
			if (nx < 1 || nx > n || ny < 1 || ny > n)
				continue;
			if (a[nx][ny] == 1 || b[nx][ny] == 1)
				continue;
			if (nx == fx && ny == fy) {
				cout << s + 1;
				return 0;
			}
			q[t].x = nx, q[t].y = ny, q[t].s = s + 1;
			t++, b[nx][ny]++;
		}
		h++;
	}
	return 0;
}