Sliding Puzzle II

• Lintcode : 794 / Leetcode : 773 similar
• Level : Hard

Problem

On a 3x3 board, there are 8 tiles represented by the integers 1 through 8, and an empty square represented by 0.

A move consists of choosing 0 and a 4-directionally adjacent number and swapping it.

Given an initial state of the puzzle board and final state, return the least number of moves required so that the initial state to final state.

If it is impossible to move from initial state to final state, return -1.

Example
Example 1:

Input:
[
 [2,8,3],
 [1,0,4],
 [7,6,5]
]
[
 [1,2,3],
 [8,0,4],
 [7,6,5]
]
Output:
4

Explanation:
[                 [
 [2,8,3],          [2,0,3],
 [1,0,4],   -->    [1,8,4],
 [7,6,5]           [7,6,5]
]                 ]

[                 [
 [2,0,3],          [0,2,3],
 [1,8,4],   -->    [1,8,4],
 [7,6,5]           [7,6,5]
]                 ]

[                 [
 [0,2,3],          [1,2,3],
 [1,8,4],   -->    [0,8,4],
 [7,6,5]           [7,6,5]
]                 ]

[                 [
 [1,2,3],          [1,2,3],
 [0,8,4],   -->    [8,0,4],
 [7,6,5]           [7,6,5]
]                 ]
Example 2：

Input:
[[2,3,8],[7,0,5],[1,6,4]]
[[1,2,3],[8,0,4],[7,6,5]]
Output:
-1
Challenge
How to optimize the memory?
Can you solve it with A* algorithm?

Concept & Algorithm

筆記

Time Complexity & Space Complexity

time : O()
space: O()

Answer

class Solution {
public:
    int minMoveStep(vector<vector<int>> &init_state, vector<vector<int>> &final_state) {
        string initString = getString(init_state);
        string finalString = getString(final_state);

        queue<pair<string, int>> q;
        set<string> repeat;
        int index = getZeroPos(initString);
        q.push({initString, index});
        repeat.insert(initString);
        int step = 0;
        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                pair<string, int> s = q.front(); q.pop();
                string res = s.first;
                int pos = s.second;

                if (res.compare(finalString) == 0) return step;
                for (auto d : dir) {
                    string str = res;
                    int x = pos / 3 + d[0];
                    int y = pos % 3 + d[1];
                    if (x < 0 || y < 0 || x >= 3 || y >= 3) continue;
                    int newIndex = x * 3 + y;
                    swap(str[newIndex], str[pos]);
                    if (repeat.find(str) != repeat.end()) continue;

                    q.push({str, newIndex});
                    repeat.insert(str);
                }
            }
            step++;
        }
        return -1;
    }
    vector<vector<int>> dir = {{1, 0}, {0, -1}, {-1, 0}, {0, 1}};
    int getZeroPos (string &s) {
        for (int i = 0; i < 9; i++) {
            if (s[i] == '0') return i;
        }
    }
    string getString (vector<vector<int>> &str) {
        string res = "";
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                res.push_back('0' + str[i][j]);
            }
        }
        return res;
    }
};

tags: BFS

​