cty_evolve edited 10 月，2 周前
我一开始没使用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();
}
}