我的代码在一些情况下最短距离要小于标准答案

cty_evolve edited 11 月,3 周前

我一开始没使用d[x][y]数组是AC了的,但是使用了d[x][y]数组之后就没有AC,不知道是什么情况

#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 210;
const int INF = 0x3f3f3f3f;
char mp[N][N];
struct Node{
    int x, y, dis;
    bool operator < (const Node &other) const {
        return dis > other.dis;
    }
};
int sx, sy, tx, ty;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int v[N][N], d[N][N];
int n, m;
void BFS(){
    memset(v, 0, sizeof v);
    memset(d, 0x3f, sizeof d);
    priority_queue<Node> q;
    Node s = {sx, sy, 0};
    d[0][0] = 0;
    q.push(s);
    while (q.size()) {
        auto [x, y, dis] = q.top(); q.pop();
        if (x == tx && y == ty) break;
        if (v[x][y]) continue;
        v[x][y] = 1;
        for (int i = 0; i < 4; i ++ ){
            int nx = x + dx[i], ny = y + dy[i];
            if (nx >= 0 && nx < m && ny >= 0 && ny < n && mp[nx][ny] != '#')
                if (mp[nx][ny] == 'X' && d[nx][ny] > dis + 2) d[nx][ny] = dis + 2, q.push({nx, ny, dis + 2});
                else if (d[nx][ny] > dis + 1) d[nx][ny] = dis + 1, q.push({nx, ny, dis + 1});
        }
    }
    if (d[tx][ty] == INF) cout << "impossible";
    else cout << d[tx][ty];
    cout << endl;
    return;
}
int main(){
    cin.tie(0);
    while(cin >> m >> n) {
        memset(mp, 0, sizeof mp);
        for (int i = 0; i < m; i ++ ) cin >> mp[i];
        for (int i = 0; i < m; i ++ ) 
            for (int j = 0; j < n; j ++ )
                if (mp[i][j] == 'S') sx = i, sy = j;
                else if (mp[i][j] == 'T') tx = i, ty = j;
        
        BFS();
            
    }
}

Comments