AOJ2391

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