有没有深搜的，求助

YHL_RP @ 2024-12-18 19:23:42

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

const int N = 1005;
int n, dt[N][N];
int x1, x2, y1s, y2s, ans = INT_MAX;
int GoX[4] = {0, -1, 0, 1};
int GoY[4] = {-1, 0, 1, 0};

void dfs(int x, int y, int level) {
    if (x > n || x < 1 || y < 1 || y > n || dt[x][y] == 1) {
        return;
    }
    if (x == x2 && y == y2s) {
        ans = min(ans, level);
    }
    dt[x][y] = 1;
    for (int i = 0; i < 4; i++) {
        dfs(x + GoX[i], y + GoY[i], level + 1);
    }
    dt[x][y] = 0;
    return;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            char temp;
            cin >> temp;
            dt[i][j] = temp - '0';
        }
    }
    cin >> x1 >> y1s >> x2 >> y2s;
    dfs(x1, y1s, 0);
    cout << ans;
    return 0;
}

by YHL_RP @ 2024-12-18 19:45:37

广搜MLE！

#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++) {
            if ((x + GoX[i] <= n && x + GoX[i] >= 1) && (y + GoY[i] <= n && y + GoY[i] >= 1) && dt[x + GoX[i]][y + GoY[i]] != '1') {
                q.push({x + GoX[i], y + GoY[i]});
                dis[x + GoX[i]][y + GoY[i]] = dis[x][y] + 1;
            }
        }
    }
    cout << dis[x2][y2s];
    return 0;
}