Skip to content

773. Sliding Puzzle 👍

  • Time: $O((mn)!)$
  • Space: $O((mn)!)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
 public:
  int slidingPuzzle(vector<vector<int>>& board) {
    constexpr int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    constexpr int m = 2;
    constexpr int n = 3;
    const string goal = "123450";
    int steps = 0;
    string start;

    // Hash the 2D vector into a string.
    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        start += '0' + board[i][j];

    if (start == goal)
      return 0;

    queue<string> q{{start}};
    unordered_set<string> seen{start};

    while (!q.empty()) {
      ++steps;
      for (int sz = q.size(); sz > 0; --sz) {
        string s = q.front();
        q.pop();
        const int zeroIndex = s.find('0');
        const int i = zeroIndex / n;
        const int j = zeroIndex % n;
        for (const auto& [dx, dy] : dirs) {
          const int x = i + dx;
          const int y = j + dy;
          if (x < 0 || x == m || y < 0 || y == n)
            continue;
          const int swappedIndex = x * n + y;
          swap(s[zeroIndex], s[swappedIndex]);
          if (s == goal)
            return steps;
          if (!seen.contains(s)) {
            q.push(s);
            seen.insert(s);
          }
          swap(s[zeroIndex], s[swappedIndex]);
        }
      }
    }

    return -1;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
  public int slidingPuzzle(int[][] board) {
    final int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    final int m = 2;
    final int n = 3;
    final String goal = "123450";
    int steps = 0;
    StringBuilder startSb = new StringBuilder();

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        startSb.append((char) ('0' + board[i][j]));

    final String start = startSb.toString();

    if (start.equals(goal))
      return 0;

    Queue<String> q = new ArrayDeque<>(Arrays.asList(start));
    Set<String> seen = new HashSet<>(Arrays.asList(start));

    while (!q.isEmpty()) {
      ++steps;
      for (int sz = q.size(); sz > 0; --sz) {
        final String s = q.poll();
        final int zeroIndex = s.indexOf("0");
        final int i = zeroIndex / n;
        final int j = zeroIndex % n;
        for (int[] dir : dirs) {
          final int x = i + dir[0];
          final int y = j + dir[1];
          if (x < 0 || x == m || y < 0 || y == n)
            continue;
          final int swappedIndex = x * n + y;
          StringBuilder sb = new StringBuilder(s);
          sb.setCharAt(zeroIndex, s.charAt(swappedIndex));
          sb.setCharAt(swappedIndex, s.charAt(zeroIndex));
          final String t = sb.toString();
          if (t.equals(goal))
            return steps;
          if (!seen.contains(t)) {
            q.offer(t);
            seen.add(t);
          }
        }
      }
    }

    return -1;
  }
}