ALDS1_13-C.cpp

#include <bits/stdc++.h>

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()

using namespace std;

const int dx[4] = {-4, -1, 1, 4};

typedef array<int,16> Table;

struct Board {
  Table t;
  Board () {
    REP(i,16) t[i] = (i + 1) % 16;
  }
  Board (Table s) : t(s) {}
  bool move(int dir) {
    int x = 0;
    REP(i,16) if (t[i] == 0) x = i;
    if (dir == 2 && x % 4 == 3) return false;
    if (dir == 1 && x % 4 == 0) return false;
    int nx = x + dx[dir];
    if (nx < 0 || nx > 15) return false;
    swap(t[x], t[nx]); x = nx;
    return true;
  }
  int eval() {
    int sum = 0;
    REP(i,4) REP(j,4) {
      if (t[i*4+j] == 0) continue;
      int y = (t[i*4+j] + 15) % 16 / 4;
      int x = (t[i*4+j] + 3) % 4;
      sum += abs(i - y) + abs(j - x);
    }
    return -sum;
  }
  bool operator==(const Board &rhs) { return t == rhs.t; }
  bool operator<(const Board &rhs) const { return t < rhs.t; }
};

set<Board> searched;

int solve() {
  Table start;
  REP(i,16) cin >> start[i];
  Board goal;
  priority_queue<tuple<int,int,Board>> que;
  Board st(start);
  if (st == goal) return 0;
  que.push(make_tuple(st.eval(), 0, st));
  while (!que.empty()) {
    int c = get<1>(que.top());
    Board b = get<2>(que.top());
    que.pop();
    REP(i,4) {
      Board nb = b;
      bool flag = nb.move(i);
      if (flag && searched.find(nb) == searched.end()) {
        if (nb == goal) return c + 1;
        searched.insert(nb);
        int ev = nb.eval();
        que.push(make_tuple(ev - c - 1, c + 1, nb));
      }
    }
  }
  return -1;
}

int main() {
  cout << solve() << endl;
  return 0;
}