773.md

773. Sliding Puzzle

Solution 1 (time O((23)!(23)), space O((23)!))

# BFS
class Solution {
public:
    int slidingPuzzle(vector<vector<int>>& board) {
        string end = "123450";
        string start = "";
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 3; j++) {
                start += to_string(board[i][j]);
            }
        }
        if (start == end) {
            return 0;
        }
        queue <pair <string, int>> q;
        q.push(make_pair(start, 0));
        unordered_set<string> vis = {start};
        while (!q.empty()) {
            pair <string, int> cur_pair = q.front();
            q.pop();
            string cur_state = cur_pair.first;
            int cur_level = cur_pair.second;
            string new_state;
            int ind;
            char temp;
            for (int i = 0; i < 6; i++) {
                if (cur_state[i] == '0') {
                    ind = i;
                }
            }
            
            if (ind == 3 || ind == 4 || ind == 5) {
                new_state = cur_state;
                temp = new_state[ind];
                new_state[ind] = new_state[ind - 3];
                new_state[ind - 3] = temp;
                if (new_state == end) {
                    return cur_level + 1;
                }
                if (!vis.count(new_state)){
                    vis.insert(new_state);
                    q.push(make_pair(new_state, cur_level + 1));
                }
            }

            if (ind == 0 || ind == 1 || ind == 2) {
                new_state = cur_state;
                temp = new_state[ind];
                new_state[ind] = new_state[ind + 3];
                new_state[ind + 3] = temp;
                if (new_state == end) {
                    return cur_level + 1;
                }
                if (!vis.count(new_state)){
                    vis.insert(new_state);
                    q.push(make_pair(new_state, cur_level + 1));
                }
            }

            if (ind == 1 || ind == 2 || ind == 4 || ind == 5) {
                new_state = cur_state;
                temp = new_state[ind];
                new_state[ind] = new_state[ind - 1];
                new_state[ind - 1] = temp;
                if (new_state == end) {
                    return cur_level + 1;
                }
                if (!vis.count(new_state)){
                    vis.insert(new_state);
                    q.push(make_pair(new_state, cur_level + 1));
                }
            }

            if (ind == 0 || ind == 1 || ind == 3 || ind == 4) {
                new_state = cur_state;
                temp = new_state[ind];
                new_state[ind] = new_state[ind + 1];
                new_state[ind + 1] = temp;
                if (new_state == end) {
                    return cur_level + 1;
                }
                if (!vis.count(new_state)){
                    vis.insert(new_state);
                    q.push(make_pair(new_state, cur_level + 1));
                }
            }
        }
        return -1;
    }
};