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; }