求助大佬 40 pts 其余全 RE

yuchenren @ 2021-10-07 16:09:13

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

struct NODE {
    int x, y;
};

queue <NODE> q;

int n, x, y, nextx, nexty, dis[1001][1001], instartx, instarty, tarx, tary, dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
char MAP[1001][1001];
bool vis[1001][1001];

int bfs(int startx, int starty) {
    q.push((NODE){startx, starty});
    vis[startx][starty] = true;
    while (!q.empty()) {
        x = q.front().x;
        y = q.front().y;
        q.pop();
        if (x == tarx && y == tary) {
            return dis[x][y];
        }
        for (int i = 0; i < 4; i++) {
            nextx = x + dx[i];
            nexty = y + dy[i];
            if ((MAP[nextx][nexty] == '1' || vis[nextx][nexty] == true) || (nextx <= 0 || nextx > n || nexty <= 0 || nexty > n)) {
                continue;
            }
            dis[nextx][nexty] = dis[x][y] + 1;
            vis[nextx][nexty] = true;
            q.push((NODE){nextx, nexty});
        }
    }
    return -1;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> MAP[i][j];
        }
    }
    cin >> instartx >> instarty >> tarx >> tary;
    cout << bfs(instartx, instarty) << endl;
    return 0;
}

by qfpjm @ 2021-10-07 16:31:50

改成这样

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

struct NODE {
    int x, y;
};

queue <NODE> q;

int n, x, y, nextx, nexty, dis[10001][1001], instartx, instarty, tarx, tary, dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
char MAP[10001][1001];
bool vis[10001][1001];

int bfs(int startx, int starty) {
    q.push((NODE){startx, starty});
    vis[startx][starty] = true;
    while (!q.empty()) {
        x = q.front().x;
        y = q.front().y;
        q.pop();
        if (x == tarx && y == tary) {
            return dis[x][y];
        }
        for (int i = 0; i < 4; i++) {
            nextx = x + dx[i];
            nexty = y + dy[i];
            if ((MAP[nextx][nexty] == '1' || vis[nextx][nexty] == true) || (nextx <= 0 || nextx > n || nexty <= 0 || nexty > n)) {
                continue;
            }
            dis[nextx][nexty] = dis[x][y] + 1;
            vis[nextx][nexty] = true;
            q.push((NODE){nextx, nexty});
        }
    }
    return -1;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> MAP[i][j];
        }
    }
    cin >> instartx >> instarty >> tarx >> tary;
    cout << bfs(instartx, instarty) << endl;
    return 0;
}

by qfpjm @ 2021-10-07 16:32:15

@任宇宸

by yuchenren @ 2021-10-07 16:36:07

@Ted何家乐 AC 了，感谢！！！