773. Sliding Puzzle, C++ (gcc)

773. Sliding Puzzle

class Solution {
    int convert(const vector<int>& v) {
        int res = 0;
        for (auto i : v) res = res * 10 + i;
        return res;
    }
    
    int convert (const vector<vector<int>>& mat) {
        vector<int> linerizedMat = {};
        for (auto r : mat) {
            for (auto c : r) linerizedMat.push_back(c);
        }
        
        return convert(linerizedMat);
    }
    
    vector<vector<int>> toGrid (int state) {
        vector<vector<int>> mat(2, vector<int>(3, 0));
        string s = to_string(state);
        
        int ind = 0;
        if (s.length() < 6) ind --;
        
        for (int r = 0; r < 2; r ++) {
            for (int c = 0; c < 3; c ++) {
                if (ind < 0) {
                    ind ++;
                    continue;
                }
                
                mat[r][c] = s[ind++] - '0';
            }
        }
        
        return mat;
    }
    
    vector<int> neighbors (int state) {
        vector<vector<int>> mat = toGrid(state);
        
        vector<int> result;
        
        vector<vector<int>> moves = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
        for (int r = 0; r < 2; r ++) {
            for (int c = 0; c < 3; c ++) {
                if (mat[r][c]) continue;
                
                for (auto move : moves) {
                    int new_r = move[0] + r;
                    int new_c = move[1] + c;
                    
                    bool valid = new_r >= 0 && new_r < 2 && new_c >= 0 && new_c < 3;
                    if (!valid) continue;
                    
                    swap (mat[new_r][new_c], mat[r][c]);
                    result.push_back(convert(mat));
                    swap (mat[new_r][new_c], mat[r][c]);
                }
            }
        }
        
        return result;
        
    }
    
    void permute(int mask, vector<int>& cur, int ind, vector<int>& all) {
        if (ind == 6) {
            all.push_back(convert(cur));
            return;
        }
        
        for (int i = 0; i < 6; i ++) {
            if ((1 << i) & mask) continue;
            cur.push_back(i);
            permute (mask | (1 << i), cur, ind+1, all);
            cur.pop_back();
        }
    }
    
public:
    int slidingPuzzle(vector<vector<int>>& board) {
        vector<int> all;
        vector<int> tmp;
        permute(0, tmp,  0, all);
        
        
        map<int, vector<int>> graph;
        for (auto i : all) {
            vector<int> neig = neighbors (i);
            
            // cout << i << " -> ";
            // for (auto t : neig) cout << t << " "; 
            // cout << endl;
            
            for (auto e : neig) graph[i].push_back(e);
        }
        
        vector<vector<int>> finalStateMatrix = {{1, 2, 3}, {4, 5, 0}};
        int finalState = convert(finalStateMatrix);
        
        queue<pair<int, int>> q;
        map<int, bool> vis;
        
        q.push({convert(board), 0});
        vis[convert(board)] = true;
        
        while (!q.empty()) {
            int state = q.front().first;
            int cost = q.front().second;
            q.pop();
            
            if (state == finalState) return cost;
            for (auto i : graph[state]) {
                bool alreadyVisited = vis.find(i) != vis.end();
                if (alreadyVisited) continue;
                
                q.push({i, cost+1});
                vis[i] = true;
            }
        }
        
        return -1;
    }
};


run \| edit \| history \| help	0

λ

                                      .NET NoSQL database for rapid development