POJ_1077_BFS.cpp

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

using namespace std;

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

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

struct Direction {
  char c;
  int x;
  int y;
  Direction(char _c, int _x, int _y) : c(_c), x(_x), y(_y) {}
};

class SlidingPuzzle {
public:
  string bfs(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> distances;
    queue<State> q;
    distances[source.key] = 0;
    q.push(source);
    prevs[source.key] = pair<int, char>(-1, '$');

    while (!q.empty()) {
      State current = q.front();
      q.pop();

      int distance = distances[current.key] + 1;
      int zeropos = current.board[9];
      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;
        swap(next.board[zeropos], next.board[nextpos]);
        next.board[9] = (char)nextpos;
        next.key = lehmer(next.board);
        if (prevs.find(next.key) == prevs.end() || distances[next.key] > distance) {
          prevs[next.key] = pair<int, char>(current.key, direction.c);
          distances[next.key] = distance;
          q.push(next);
        }
      }
    }

    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;
      source.board[9] = i;
    } else {
      source.board[i] = c - '0';
    }
  }
  source.key = lehmer(source.board);

  char targetBoard[] = {1, 2, 3, 4, 5, 6, 7, 8, 0, 8};
  copy(targetBoard, targetBoard + 10, target.board);
  target.key = lehmer(target.board);

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