求条
查看原帖
求条
931664
sieve楼主2025/1/17 15:40

rt,dijkstra 二维转一维模板过了 99 个点,WA 了 55 个点。

#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;
}
2025/1/17 15:40
加载中...