30分求助,样例都过不了
查看原帖
30分求助,样例都过不了
681755
CuteGirlGC楼主2024/1/8 20:27
#include <cstring>
#include <iostream>
#include <queue>

using namespace std;

const int kMaxN = 102, kTo[4][2] = {{3, 1}, {0, 2}, {1, 3}, {2, 0}}, kD[4][2] = {{1, 0}, {0, -1}, {-1, 0}, {0, 1}};

bool f[kMaxN][kMaxN];
int n, m, sx, sy, sd, ex, ey, ds[kMaxN][kMaxN][kMaxN];
struct Node {
  int x, y, s, d;
  Node(int x, int y, int d, int s) : x(x), y(y), s(s), d(d) {}
};
queue<Node> q;

void REcord(int nx, int ny, int nd, int s) {
  if (nx < 1 || ny < 1 || nx > n || ny > m || ds[nx][ny][nd] <= s || f[nx][ny]) {
    return;
  }
  ds[nx][ny][nd] = s;
  q.push(Node(nx, ny, nd, s));
}

int Bfs() {
  memset(ds, 0x3f, sizeof(ds)), ds[sx][sy][sd] = 0;
  q.push(Node(sx, sy, sd, 0));
  while (!q.empty()) {
    Node t = q.front();
    // cerr << t.x << ' ' << t.y << ' ' << t.s << ' ' << t.d << '\n';
    q.pop();
    int o = 1;
    int nx = t.x + kD[t.d][0], ny = t.y + kD[t.d][1];
    for (int i = 1; i <= 2; i++) {
      REcord(nx, ny, t.d, t.s + 1);
      int tx = nx + kD[t.d][0], ty = ny + kD[t.d][1];
      if (tx < 1 || tx > n || ty < 1 || ty > m || f[nx][ny]) {
        break;
      }
      nx = tx, ny = ty, o++;
    }
    REcord(nx, ny, t.d, t.s + 1);
    REcord(t.x + kD[kTo[t.d][0]][0], t.y + kD[kTo[t.d][0]][0], kTo[t.d][0], t.s + 1);
    REcord(t.x + kD[kTo[t.d][1]][0], t.y + kD[kTo[t.d][1]][0], kTo[t.d][1], t.s + 1);
  }
  int ans = 1e9;
  for (int i = 0; i < 4; i++) {
    ans = min(ans, ds[ex][ey][i]);
  }
  return ans == 1e9 ? -1 : ans;
}

int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      bool o;
      cin >> o;
      f[i][j] |= o, f[i - 1][j - 1] |= o;
      f[i - 1][j] |= o, f[i][j - 1] |= o;
    }
  }
  cin >> sx >> sy >> ex >> ey;
  char c;
  cin >> c;
  sd = (c != 'S') + (c == 'N') + 2 * (c == 'E');
  // cout << sd << '\n';
  cout << Bfs() << '\n';
  return 0;
}

记录

2024/1/8 20:27
加载中...