Codeforces Round #354 Div2 D: Theseus and labyrinth

問題

Problem - D - Codeforces

解法

筋肉ダイクストラ

コード

#include <bits/stdc++.h>
using namespace std;

template <class T, class U>
void chmin(T &t, U f) {
  if (t > f) t = f;
}

typedef tuple<int, int, int, int> P;  // dist, layer, h,w

const int INF = 1e9, LAYERS = 4;
const int RIGHT = 0, LEFT = 1, DOWN = 2, UP = 3;
const string US = "+|^LRD";
const string DS = "+|vLRU";
const string LS = "+-<RUD";
const string RS = "+->UDL";
const int DH[] = {0, 0, 1, -1};
const int DW[] = {1, -1, 0, 0};

int H, W;

char getlayerblock(char c, int layer) {
  if (layer == 0) return c;
  switch (c) {
    case '+':
      return '+';
    case '*':
      return '*';
    case '-':
      if (layer == 2) return '-';
      return '|';
    case '|':
      if (layer == 2) return '|';
      return '-';
    case '^':
      if (layer == 1) return '>';
      if (layer == 2) return 'v';
      if (layer == 3) return '<';
    case '>':
      if (layer == 1) return 'v';
      if (layer == 2) return '<';
      if (layer == 3) return '^';
    case 'v':
      if (layer == 1) return '<';
      if (layer == 2) return '^';
      if (layer == 3) return '>';
    case '<':
      if (layer == 1) return '^';
      if (layer == 2) return '>';
      if (layer == 3) return 'v';
    case 'R':
      if (layer == 1) return 'D';
      if (layer == 2) return 'L';
      if (layer == 3) return 'U';
    case 'D':
      if (layer == 1) return 'L';
      if (layer == 2) return 'U';
      if (layer == 3) return 'R';
    case 'L':
      if (layer == 1) return 'U';
      if (layer == 2) return 'R';
      if (layer == 3) return 'D';
    case 'U':
      if (layer == 1) return 'R';
      if (layer == 2) return 'D';
      if (layer == 3) return 'L';
    default:
      break;
  }
  assert(false);
  return c;
}

bool cango(const vector<string> &maze, int layer, int h, int w, int dir) {
  int nh = h + DH[dir];
  int nw = w + DW[dir];
  if (nh < 0 || nh >= H) return false;
  if (nw < 0 || nw >= W) return false;
  char now = getlayerblock(maze[h][w], layer);
  char next = getlayerblock(maze[nh][nw], layer);
  if (dir == UP) {
    bool ok1 = false, ok2 = false;
    for (char c : US)
      if (c == now) ok1 = true;
    for (char c : DS)
      if (c == next) ok2 = true;
    if (ok1 && ok2) return true;
    return false;
  }
  if (dir == DOWN) {
    bool ok1 = false, ok2 = false;
    for (char c : DS)
      if (c == now) ok1 = true;
    for (char c : US)
      if (c == next) ok2 = true;
    if (ok1 && ok2) return true;
    return false;
  }
  if (dir == RIGHT) {
    bool ok1 = false, ok2 = false;
    for (char c : RS)
      if (c == now) ok1 = true;
    for (char c : LS)
      if (c == next) ok2 = true;
    if (ok1 && ok2) return true;
    return false;
  }
  if (dir == LEFT) {
    bool ok1 = false, ok2 = false;
    for (char c : LS)
      if (c == now) ok1 = true;
    for (char c : RS)
      if (c == next) ok2 = true;
    if (ok1 && ok2) return true;
    return false;
  }
  assert(false);
  return false;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  cin >> H >> W;
  vector<string> maze(H);
  for (int i = 0; i < H; ++i) cin >> maze[i];

  int sh, sw, gh, gw;
  cin >> sh >> sw >> gh >> gw;
  sh--, sw--, gh--, gw--;

  vector<vector<int>> dist[4];
  for (int i = 0; i < 4; ++i) dist[i].assign(H, vector<int>(W, INF));
  priority_queue<P, vector<P>, greater<P>> Q;
  Q.emplace(0, 0, sh, sw);
  dist[0][sh][sw] = 0;
  while (!Q.empty()) {
    int d, layer, h, w;
    tie(d, layer, h, w) = Q.top();
    Q.pop();
    for (int dir = 0; dir < 4; ++dir) {
      if (!cango(maze, layer, h, w, dir)) continue;
      int nh = h + DH[dir];
      int nw = w + DW[dir];
      if (dist[layer][nh][nw] > dist[layer][h][w] + 1) {
        dist[layer][nh][nw] = dist[layer][h][w] + 1;
        Q.emplace(dist[layer][nh][nw], layer, nh, nw);
      }
    }
    int nextlayer = (layer + 1) % LAYERS;
    if (dist[nextlayer][h][w] > dist[layer][h][w] + 1) {
      dist[nextlayer][h][w] = dist[layer][h][w] + 1;
      Q.emplace(dist[nextlayer][h][w], nextlayer, h, w);
    }
  }
  int ans = INF;
  for (int i = 0; i < 4; ++i) chmin(ans, dist[i][gh][gw]);
  if (ans == INF) {
    cout << -1 << endl;
  } else {
    cout << ans << endl;
  }
}