题目描述

现在有一个 \(N\times N\) 的地图，问从起点 \((sx, sy)\) 到 \((tx,ty)\) 最少要走几步。

输入格式

第一行一个正整数 \(N\)。

接下来 \(N\) 行，每行 \(N\) 个字符，表示 \(N\times N\) 的 \(0/1\) 矩阵，\(1\) 表示不能通过，\(0\) 表示可以通过。

最后一行四个整数 \(sx,sy,tx,ty\)。

输出格式

仅有一个数，表示答案。

样例

样例输入

5
01111
00111
10001
11101
11100
1 1 5 5

样例输出

8

数据范围与提示

对于 \(100\%\) 的数据，有 \(1\leq N \leq 1000\)。

• emm，bfs模板题

#include <bits/stdc++.h>
using namespace std;

const int N = 1020;

int n;
int maze[N][N];
char c[N][N];
int d[4][2] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
int sx, sy, tx, ty;
int dis[N][N];

int main(void) {
    cin >> n;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j) {
            cin >> c[i][j];
            maze[i][j] = c[i][j] - 48;
        }
    cin >> sx >> sy >> tx >> ty;

    queue<pair<int, int> > q;
    q.push(make_pair(sx, sy));
    maze[sx][sy] = 1;
    dis[sx][sy] = 0;

    while (q.size()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        if (x == tx && y == ty) {
            cout << dis[x][y];
            return 0;
        }

        for (int i = 0; i < 4; ++i) {
            int xx = x + d[i][0];
            int yy = y + d[i][1];

            if (xx < 1 || xx > n)
                continue;
            if (yy < 1 || yy > n)
                continue;
            if (maze[xx][yy])
                continue;

            maze[xx][yy] = 1;
            dis[xx][yy] = dis[x][y] + 1;

            q.push(make_pair(xx, yy));
        }
    }

    return 0;
}