LC773_ASTAR_1.cpp

class Solution {
private:
  struct State {
    string key;
    vector<int> board;
    vector<int> indices;
  };
  
  string encode(vector<int>& vec) {
    string result = "";
    for (int x : vec) {
      result += (char)(x + '0');
    }
    return result;
  }
  
  vector<int> flatten(vector<vector<int>>& board) {
    vector<int> result;
    for (auto& vec: board) {
      result.insert(result.end(), vec.begin(), vec.end());
    }
    return result;
  }
  
  int heuristic(State& a, State& b) {
    int result = 0;
    for(int i = 0; i < 6; ++i) {
      result += heuristic(a, b, i);
    }
    return result;
  }
  
  int heuristic(State& a, State& b, int x) {
    int ai = a.indices[x];
    int bi = b.indices[x];
    int m = 3;
    if (ai == bi) {
      return 0;
    }
    return abs((ai % m) - (bi % m)) + abs((ai / m) - (bi / m));
  }
  
  struct Compare {
    bool operator () (const pair<int, State>& a, const pair<int, State>& b) const {
      return a.first > b.first;
    }
  };
  
  int astar(State& source, State& target, int n, int m) {
    vector<int> directions = {-1, 0, 1, 0, 0, -1, 0, 1};
    unordered_map<string, int> groundDistances;
    priority_queue<pair<int, State>, vector<pair<int, State>>, Compare> pq;
    groundDistances[source.key] = 0;
    pq.push(pair<int, State>(heuristic(source, target), source));
    
    while (!pq.empty() && groundDistances.find(target.key) == groundDistances.end()) {
      State curState = pq.top().second;
      int curF = pq.top().first;
      pq.pop();
      int curGround = groundDistances[curState.key];
      int curH = curF - curGround;
      int center = curState.indices[0];
      int cx = center % m;
      int cy = center / m;
      for (int i = 0; i < directions.size(); i += 2) {
        int nx = cx + directions[i];
        int ny = cy + directions[i + 1];
        if (nx < 0 || ny < 0 || nx >= m || ny >= n) {
          continue;
        }
        State nextState = curState;
        int nextPos = ny * m + nx;
        swap(nextState.indices[curState.board[center]], nextState.indices[curState.board[nextPos]]);
        swap(nextState.board[center], nextState.board[nextPos]);
        nextState.key = encode(nextState.board);
        int nextH = curH;
        nextH -= heuristic(curState, target, curState.board[center]);
        nextH -= heuristic(curState, target, curState.board[nextPos]);
        nextH += heuristic(nextState, target, curState.board[center]);
        nextH += heuristic(nextState, target, curState.board[nextPos]);
        
        int nextG = curGround + 1;
        int nextF = nextH + nextG;
        if (groundDistances.find(nextState.key) == groundDistances.end() || groundDistances[nextState.key] > nextG) {
          groundDistances[nextState.key] = nextG;
          pq.push(pair<int, State>(nextF, nextState));
        }
      }
    }
    return groundDistances.find(target.key) == groundDistances.end() ? -1 : groundDistances[target.key];
  }
public:
  int slidingPuzzle(vector<vector<int>>& board) {
    State source;
    State target;
    source.board = flatten(board);
    target.board = {1, 2, 3, 4, 5, 0};
    source.key = encode(source.board);
    target.key = encode(target.board);
    source.indices.resize(6);
    target.indices.resize(6);
    for (int i = 0; i < 6; ++i) {
      source.indices[source.board[i]] = i;
      target.indices[target.board[i]] = i;
    }
    return astar(source, target, board.size(), board[0].size());
  }
};