POJ_1077_ASTAR.cpp

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <algorithm>

using namespace std;

struct State {
  int key;
  // first 9: board, use the last one for zero position
  char board[9];
  char indices[9];
};

vector<int> factorials = {1, 1, 2, 6, 24, 120, 720, 5040, 40320};

int lehmer(char* board) {
  int result = 0;
  for (int i = 0; i < 9; ++i) {
    int a = board[i];
    for (int k = 0; k < i; ++k) {
      if (board[k] < board[i]) {
        --a;
      }
    }
    result += a * factorials[8 - i];
  }
  return result;
}

class SlidingPuzzle {
private:
  int manhattan(char a, char b) {
    int ax = a % 3;
    int ay = a / 3;
    int bx = b % 3;
    int by = b / 3;
    return abs(ax - bx) + abs(ay - by);
  }

  int manhattan(char* a, char* b) {
    int result = 0;
    for (int i = 0; i < 9; ++i) {
      result += manhattan(a[i], b[i]);
    }
    return result;
  }

  struct Direction {
    char c;
    int x;
    int y;
    Direction(char _c, int _x, int _y) : c(_c), x(_x), y(_y) {}
  };
public:
  string astar(State& source, State& target) {
    string result = "";
    unordered_map<int, pair<int, char>> prevs;
    vector<Direction> directions = {
      Direction('u', 0, -1),
      Direction('d', 0, +1),
      Direction('l', -1, 0),
      Direction('r', +1, 0)
    };
    unordered_map<int, int> groundmap;
    unordered_map<int, State> buffer = {{source.key, source}};
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    groundmap[source.key] = 0;
    pq.push(pair<int, int>(manhattan(source.indices, target.indices), source.key));
    prevs[source.key] = pair<int, char>(-1, '$');
    unordered_set<int> visited;

    while (!pq.empty()) {
      int currentKey = pq.top().second;
      if (currentKey == target.key) {
        break;
      }
      if (visited.find(currentKey) != visited.end()) {
        pq.pop();
        continue;
      }
      State& current = buffer[currentKey];
      int curF = pq.top().first;
      pq.pop();
      visited.insert(current.key);
      int curG = groundmap[current.key];
      int curH = curF - curG;
      int zeropos = current.indices[0];
      int zerox = zeropos % 3;
      int zeroy = zeropos / 3;

      for (auto& direction : directions) {
        int nextx = zerox + direction.x;
        int nexty = zeroy + direction.y;
        if (nextx < 0 || nextx >= 3 || nexty < 0 || nexty >= 3) {
          continue;
        }
        State next = current;
        int nextpos = nexty * 3 + nextx;

        char movedChar = current.board[nextpos];
        swap(next.board[zeropos], next.board[nextpos]);
        swap(next.indices[0], next.indices[movedChar]);
        next.key = lehmer(next.board);
        if (visited.find(next.key) != visited.end()) {
          continue;
        }
        int nextG = curG + 1;
        if (groundmap.find(next.key) == groundmap.end() || groundmap[next.key] > nextG) {
          prevs[next.key] = pair<int, char>(current.key, direction.c);
          groundmap[next.key] = nextG;
          int nextH = curH;
          nextH -= manhattan(current.indices[0], target.indices[0]);
          nextH -= manhattan(current.indices[movedChar], target.indices[movedChar]);
          nextH += manhattan(next.indices[0], target.indices[0]);
          nextH += manhattan(next.indices[movedChar], target.indices[movedChar]);
          int nextF = nextG + nextH;
          buffer[next.key] = next;
          pq.push(pair<int, int>(nextF, next.key));
        }
      }
    }

    if (prevs.find(target.key) == prevs.end()) {
      return "unsolvable";
    }

    int cur = target.key;
    while (cur != source.key) {
      result += prevs[cur].second;
      cur = prevs[cur].first;
    }
    reverse(result.begin(), result.end());
    return result;
  }
};

int main() {
  State source;
  State target;
  for (int i = 0; i < 9; ++i) {
    char c;
    cin >> c;
    if (c == 'x') {
      source.board[i] = 0;
    } else {
      source.board[i] = c - '0';
    }
  }
  source.key = lehmer(source.board);

  char targetBoard[] = {1, 2, 3, 4, 5, 6, 7, 8, 0};
  copy(targetBoard, targetBoard, target.board);
  for (int i = 0; i < 9; ++i) {
    source.indices[source.board[i]] = i;
    target.indices[target.board[i]] = i;
  }
  target.key = lehmer(target.board);

  cout << SlidingPuzzle().astar(source, target) << endl;
  return 0;
}