RUPC 2016 Day2 E: Rubik Dungeon

解法

回転と回転の間には移動を挟まなそう、みたいな適当な気持ちで適当に書いたら通ってしまった。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template <typename T>
std::ostream &operator<<(std::ostream &out, const std::vector<T> &v) {
  if (!v.empty()) {
    out << '[';
    std::copy(v.begin(), v.end(), std::ostream_iterator<T>(out, ", "));
    out << "\b\b]";
  }
  return out;
}
template <typename T1, typename T2>
std::ostream &operator<<(std::ostream &out, const std::pair<T1, T2> &p) {
  out << "[" << p.first << ", " << p.second << "]";
  return out;
}
template <class T, class U>
void chmin(T &t, U f) {
  if (t > f) t = f;
}
template <class T, class U>
void chmax(T &t, U f) {
  if (t < f) t = f;
}

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

  int N;
  cin >> N;
  int sx, sy, sz;
  cin >> sx >> sy >> sz;
  int tx, ty, tz;
  cin >> tx >> ty >> tz;
  map<tuple<int, int, int>, int> dist;
  dist[make_tuple(sx, sy, sz)] = 0;
  for (int i = 0; i < 3; ++i) {
    vector<pair<tuple<int, int, int>, int>> tmp;
    for (const auto &p : dist) {
      int x, y, z;
      tie(x, y, z) = p.first;
      int d = p.second;
      if (x > 0) tmp.push_back({make_tuple(x - 1, y, z), d + 1});
      if (y > 0) tmp.push_back({make_tuple(x, y - 1, z), d + 1});
      if (z > 0) tmp.push_back({make_tuple(x, y, z - 1), d + 1});
      if (x < N - 1) tmp.push_back({make_tuple(x + 1, y, z), d + 1});
      if (y < N - 1) tmp.push_back({make_tuple(x, y + 1, z), d + 1});
      if (z < N - 1) tmp.push_back({make_tuple(x, y, z + 1), d + 1});
    }
    for (const auto &p : tmp)
      if (!dist.count(p.first) || dist[p.first] > p.second)
        dist[p.first] = p.second;
  }

  for (int i = 0; i < 3; ++i) {
    vector<pair<tuple<int, int, int>, int>> tmp;
    for (const auto &p : dist) {
      int x, y, z;
      tie(x, y, z) = p.first;
      int d = p.second;
      if (z != tz) tmp.push_back({make_tuple(y, N - 1 - x, z), d + 1});
      if (z != tz) tmp.push_back({make_tuple(N - 1 - y, x, z), d + 1});
      if (x != tx) tmp.push_back({make_tuple(x, z, N - 1 - y), d + 1});
      if (x != tx) tmp.push_back({make_tuple(x, N - 1 - z, y), d + 1});
      if (y != ty) tmp.push_back({make_tuple(N - 1 - z, y, x), d + 1});
      if (y != ty) tmp.push_back({make_tuple(z, y, N - 1 - x), d + 1});
    }
    for (const auto &p : tmp)
      if (!dist.count(p.first) || dist[p.first] > p.second)
        dist[p.first] = p.second;
  }

  int mi = N * 4;
  for (const auto &p : dist) {
    int x, y, z;
    tie(x, y, z) = p.first;
    int d = p.second + abs(tx - x) + abs(ty - y) + abs(tz - z);
    chmin(mi, d);
  }
  cout << mi << endl;
}