为什么会MLE

P1746 离开中山路

YHL_RP @ 2024-12-18 19:51:53

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

const int N = 1001;
char dt[N][N];
int n, dis[N][N];
int x1, x2, y1s, y2s;
int GoX[4] = {0, -1, 0, 1};
int GoY[4] = {-1, 0, 1, 0};

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> dt[i][j];
        }
    }
    cin >> x1 >> y1s >> x2 >> y2s;
    queue<pair<int, int>> q;
    q.push({x1, y1s});
    dt[x1][y1s] = '1';

    while(q.size()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        dt[x][y] = '1';
        for (int i = 0; i < 4; i++) {
            int tx = x + GoX[i];
            int ty = y + GoY[i];
            if (tx <= n && tx >= 1 && ty <= n && ty >= 1 && dt[tx][ty] != '1') {
                q.push({tx, ty});
                dis[tx][ty] = dis[x][y] + 1;
            }
        }
    }
    cout << dis[x2][y2s];
    return 0;
}

by 违规用户名971024 @ 2024-12-18 20:00:49

因为到了终点就不用走了,需要在 q.pop() 后加上判断


by 违规用户名971024 @ 2024-12-18 20:03:25

然后走过的点不能走,需要用数组标记走过的位置


by 违规用户名971024 @ 2024-12-18 20:04:11

球管 @YHL_RP


|