JAGの春コンテストのC問題
両側からBFSする。
答えが45を超えるような入力は存在しないという制約があるので、
22ステップだけ両側から探索する。
とはいっても、N<=4のときはただのBFSで事足りる。
この実装だど、メモリがぎりぎり。
キューに入れる前に終了や打ち切りの条件を確かめる必要がある。キューから取り出したモノでやるとMELする。
どちらかでも23ステップやるとMLEする。
#include <algorithm> #include <iostream> #include <map> #include <numeric> #include <queue> #include <set> #include <stack> #include <vector> #include <sstream> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <cassert> #define REP(i, n) for(int i=0; i<(int)n; ++i) #define FOR(i, c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i) #define ALL(c) (c).begin(),(c).end() #define each(i, c) FOR(i, c) #define VAR(a) cout << #a << " : " << a << endl; using namespace std; typedef long long int lli; typedef unsigned long long int Bit; const int inf = 1 << 30; const int M = 16; vector<int> adj[M]; Bit fin[M]; map<Bit, int> B; inline int idx0(Bit bit) { for (lli i = 0; ; ++i) { if (bit & (0xfLL << (i * 4))) ; else return i; } } inline Bit swap(Bit curr, int i, int j) { Bit q = curr & (0xfLL << (j * 4)); Bit next = curr ^ q ^ ((q >> (j * 4)) << (i * 4)); return next; } void backward(void) { queue<Bit> q; for (q.push(fin[15]); q.size(); q.pop()) { Bit curr = q.front(); if (B[curr] < 22) ; else continue; int i = idx0(curr); for (int k = 0; k < (int)adj[i].size(); ++k) { int j = adj[i][k]; Bit next = swap(curr, i, j); if (B.count(next)) continue; B[next] = B[curr] + 1; q.push(next); } } return ; } int forward(Bit ini, int m, int lim) { set<Bit> vis; queue< pair<Bit, int> > q; // state, cost if (ini == fin[m]) return 0; if (B.count(ini)) return B[ini]; for (q.push(make_pair(ini, 0)); q.size(); q.pop()) { pair<Bit, int> p = q.front(); Bit curr = p.first; int cost = p.second; int i = idx0(curr); for (int k = 0; k < (int)adj[i].size(); ++k) { int j = adj[i][k]; Bit next = swap(curr, i, j); if (m <= j) continue; if (next == fin[m]) return cost + 1; if (B.count(next)) return B[next] + cost + 1; if (vis.count(next)) continue; if (cost + 1 < lim) ; else continue; vis.insert(next); q.push(make_pair(next, cost + 1)); } } return 45; } int main(int argc, char *argv[]) { string s[] = {"A", "BC", "DEF", "GHIJ", "KLMNO" }; const int di[] = {-1, -1, +1, +1}; const int dj[] = {0, -1, 0, +1}; for (int i = 0; i < (int)5; ++i) { for (int j = 0; j < (int)s[i].size(); ++j) { for (int d = 0; d < 4; ++d) { int ni = i + di[d]; int nj = j + dj[d]; if (ni < 0 || nj < 0) continue; if (5 <= ni || ni < nj) continue; int a = s[i][j] - 'A'; int b = s[ni][nj] - 'A'; adj[a].push_back(b); adj[b].push_back(a); } } } for (int i = 0; i < M; ++i) { for (lli j = 0; j < i; ++j) { fin[i] |= j << (j * 4LL); } } backward(); int n; while (cin >> n && n) { int m = n * (n + 1) / 2; Bit ini = 0LL; for (int i = 0; i < (int)m; ++i) { lli x; cin >> x; ini |= (x - 1LL) << (i * 4); } static int tc = 0; cout << "Case " << ++tc << ": " << forward(ini, m, (m < 15 ? 1 << 20 : 22)) << endl; } return 0; }