Leetcode 773 BFS_1

LC773_BFS_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 bfs(State& source, State& target, int n, int m) {
    vector<int> directions = {-1, 0, 1, 0, 0, -1, 0, 1};
    unordered_map<string, int> depths;
    queue<State> q;
    q.push(source);
    depths[source.key] = 0;
    
    while (!q.empty() && depths.find(target.key) == depths.end()) {
      State curState = q.front();
      q.pop();
      int curdepth = depths[curState.key];
      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);
        if (depths.find(nextState.key) == depths.end()) {
          depths[nextState.key] = curdepth + 1;
          q.push(nextState);
        }
      }
    }
    return depths.find(target.key) == depths.end() ? -1 : depths[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 bfs(source, target, board.size(), board[0].size());
  }
};