rt,dijkstra 二维转一维模板过了 9 个点,WA 了 5 个点。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int kMaxN = 2005, kInf = 1e18, kD[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
const int kDs[][2] = {{-2, -2}, {-1, -2}, {0, -2}, {1, -2}, {2, -2}, {-2, -1}, {-1, -1}, {0, -1}, {1, -1}, {2, -1}, {-2, 0}, {-1, 0}, {1, 0}, {2, 0}, {-2, 1}, {-1, 1}, {0, 1}, {1, 1}, {2, 1}, {-2, 2}, {-1, 2}, {0, 2}, {1, 2}, {2, 2}};
int n, m, sx, sy, ex, ey;
int dis[kMaxN * kMaxN];
bool vis[kMaxN * kMaxN];
char a[kMaxN][kMaxN];
struct edge {
int v, w;
};
vector<edge> g[kMaxN * kMaxN];
int get(int x, int y) {return (x - 1) * n + y;}
struct Node {
int id, w;
bool operator<(const Node& rhs) const {
return w > rhs.w;
}
};
void dijkstra(int s) {
for (int i = 1; i <= n * m; ++i) {
dis[i] = kInf;
vis[i] = 0;
}
priority_queue<Node> q;
q.push({s, 0});
dis[s] = 0;
while (!q.empty()) {
int u = q.top().id;
q.pop();
if (vis[u]) {
continue;
}
vis[u] = 1;
for (int i = 0; i < g[u].size(); ++i) {
int v = g[u][i].v;
int w = g[u][i].w;
if (vis[v] == 0 && dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
q.push({v, dis[v]});
}
}
}
return;
}
bool check(int x, int y) {return x >= 1 && x <= n && y >= 1 && y <= m && a[x][y] == '.';}
signed main() {
cin.tie(0)->sync_with_stdio(false);
cin >> n >> m >> sx >> sy >> ex >> ey;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
cin >> a[i][j];
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
int x = i, y = j;
if (a[x][y] == '#') {
continue;
}
for (int dir = 0; dir < 24; ++dir) {
if (dir < 4) {
int nx = x + kD[dir][0], ny = y + kD[dir][1];
if (check(nx, ny)) {
g[get(x, y)].push_back({get(nx, ny), 0});
}
}
int tx = x + kDs[dir][0], ty = y + kDs[dir][1];
if (check(tx, ty)) {
g[get(x, y)].push_back({get(tx, ty), 1});
}
}
}
}
dijkstra(get(sx, sy));
cout << (dis[get(ex, ey)] == kInf ? -1 : dis[get(ex, ey)]);
return 0;
}