leetcode-go/poj/1077.eight/main.cc

#include <cstdio>
#include <cstdlib>
#include <queue>

using std::priority_queue;

#define ABS(x) ((x) < 0 ? -(x) : (x))

const int dst = 123456780;
const int S = 362880;
const int frac[9] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320};

int perm2no(int p) {
  if (p < 0) return -1;
  char perm[10];
  sprintf(perm, "%09d", p);
  bool used[9] = {};
  int n = 0;
  for (int i = 0; i < 9; i++) {
    for (int j = perm[i] - '1'; 0 <= j; j--) {
      if (used[j]) continue;
      n += frac[8 - i];
    }
    used[perm[i] - '0'] = true;
  }
  return n;
}

int no2perm(int n) {
  char perm[10];
  bool used[9] = {};
  for (int i = 0; i < 9; i++) {
    int j = n / frac[8 - i];
    n %= frac[8 - i];
    for (int k = 0; k < 9; k++) {
      if (used[k]) continue;
      if (j-- == 0) {
        used[k] = true;
        perm[i] = k + '0';
        break;
      }
    }
  }
  return atoi(perm);
}

int next_state(int p, char m) {
  char perm[10];
  sprintf(perm, "%09d", p);
  int i = 0;
  while (perm[i] != '0') i++;
  switch (m) {
    case 'u':
      if (i < 3) return -1;
      perm[i] = perm[i - 3];
      perm[i - 3] = '0';
      return atoi(perm);
    case 'd':
      if (8 < i + 3) return -1;
      perm[i] = perm[i + 3];
      perm[i + 3] = '0';
      return atoi(perm);
    case 'l':
      if (i % 3 == 0) return -1;
      perm[i] = perm[i - 1];
      perm[i - 1] = '0';
      return atoi(perm);
    case 'r':
      if (i % 3 == 2) return -1;
      perm[i] = perm[i + 1];
      perm[i + 1] = '0';
      return atoi(perm);
  }
  return -1;
}

bool even_perm(int s) {
  char perm[10];
  sprintf(perm, "%09d", s);
  int cnt = 0; // 0 is not included
  for (int i = 1; i < 9; i++) {
    if (perm[i] == '0') continue;
    for (int j = 0; j < i; j++)
      if (perm[i] < perm[j]) cnt++;
  }
  return cnt % 2 == 0;
}

struct Node {
  int s;
  int p;
  int f;
  int g;
  char m;
  Node(int s = 0, int p = 0, int f = 0, int g = 0, char m = 0)
      : s(s), p(p), f(f), g(g), m(m) {}
  bool operator<(const Node &that) const { return that.f < this->f; }
} close[S];

char moves[] = "udlr";
char res[S + 1];

int eval_h(int s) {
  int res = 0;
  for (int i = 8; 0 <= i; i--) {
    int c = s % 10;
    if (c != 0) {
      int x = (c - 1) / 3;
      int y = (c - 1) % 3;
      int cx = i / 3;
      int cy = i % 3;
      res += ABS(cx - x) + ABS(cy - y);
    }
    s /= 10;
  }
  return res;
}

bool a_star(int s) {
  if (!even_perm(s)) return false;
  int no = perm2no(s);
  close[no] = Node(s, -1);
  priority_queue<Node> pq;
  pq.push(close[no]);
  while (!pq.empty()) {
    Node cur = pq.top();
    pq.pop();
    if (cur.s == dst) return true;
    for (int i = 0; i < 4; i++) {
      char m = moves[i];
      int nxt = next_state(cur.s, m);
      no = perm2no(nxt);
      if (no == -1 || close[no].s != 0) continue;
      int h = eval_h(nxt);
      close[no] = Node(nxt, cur.s, cur.g + 1 + h, cur.g + 1, m);
      pq.push(close[no]);
    }
  }
  return false;
}

int main() {
  char perm[10];
  for (int i = 0; i < 9; i++) {
    scanf("%s", &perm[i]);
    if (perm[i] == 'x') perm[i] = '0';
  }
  int src = atoi(perm);
  if (a_star(src)) {
    int pos = perm2no(dst), i = 0;
    do {
      res[i++] = close[pos].m;
      pos = perm2no(close[pos].p);
    } while (pos != -1);  // The (i-1)th char is 0! So i - 2
    for (int j = i - 2; 0 <= j; j--) printf("%c", res[j]);
    printf("\n");
  } else {
    printf("unsolvable\n");
  }
  return 0;
}