LC773_IDASTAR_1.cpp

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

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

  vector<Direction> directions = {
    Direction('u', 0, -1),
    Direction('d', 0, +1),
    Direction('l', -1, 0),
    Direction('r', +1, 0)
  };

public:
  string idastar(State& source, State& target) {
    cout << target.key << endl;
    string result = "";
    int bound = manhattan(source.indices, target.indices);
    while (bound < 400) {
      unordered_set<int> pathset = {source.key};
      vector<State> path = {source};
      int t = search(path, result, pathset, 0, bound, target);
      if (t == 0) {
        return result;
      }
      if (t == INT_MAX) {
        return "unsolvable";
      }
      bound = t;
    }
    return result;
  }

  int search(vector<State>& path, string& result, unordered_set<int>& pathset, int g, int bound, State& target) {
    State& current = path.back();
    int curF = g + manhattan(current.indices, target.indices);
    if (curF > bound) {
      return curF;
    }
    if (current.key == target.key) {
      return 0;
    }
    int minDistance = INT_MAX;
    int zeropos = current.indices[0];
    int zerox = zeropos % 3;
    int zeroy = zeropos / 3;
    for (Direction& 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 nextChar = current.board[nextpos];
      swap(next.board[zeropos], next.board[nextpos]);
      swap(next.indices[0], next.indices[nextChar]);
      next.key = lehmer(next.board);
      if (pathset.find(next.key) == pathset.end()) {
        path.push_back(next);
        pathset.insert(next.key);
        result.push_back(direction.c);
        int t = search(path, result, pathset, g + 1, bound, target);
        // found
        if (t == 0) {
          return 0;
        }
        if (t < minDistance) {
          minDistance = t;
        }
        path.pop_back();
        pathset.erase(next.key);
        result.pop_back();
      }
    }
    return minDistance;
  }
};

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

  for (int i = 0; i < 8; ++i) {
    target.board[i] = (char)(i + 1);
  }
  target.board[8] = 0;
  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().idastar(source, target) << endl;
  return 0;
}