1
class Solution {
2
  int[][] dir = {{1, 3}, {0, 2, 4}, {1, 5}, {0, 4}, {1, 3, 5}, {2, 4}};
3

4
  public int slidingPuzzle(int[][] board) {
5

6
    String tar = "123450";
7

8
    String src = "";
9

10
    for (int i = 0; i < board.length; i++) {
11
      for (int j = 0; j < board[i].length; j++) {
12
        src += board[i][j];
13
      }
14
    }
15

16
    HashSet<String> visited = new HashSet<>();
17

18
    visited.add(src);
19
    int level = 0;
20
    ArrayDeque<String> q = new ArrayDeque<>();
21
    q.add(src);
22
    while (q.size() != 0) {
23
      int t = q.size();
24

25
      while (t-- > 0) {
26
        String rem = q.remove();
27

28
        if (rem.equals(tar)) {
29
          return level;
30
        }
31

32
        int idx = -1;
33

34
        for (int i = 0; i < rem.length(); i++) {
35
          if (rem.charAt(i) == '0') {
36
            idx = i;
37
            break;
38
          }
39
        }
40

41
        for (int i = 0; i < dir[idx].length; i++) {
42
          String str = swapEle(rem, idx, dir[idx][i]);
43

44
          if (!visited.contains(str)) {
45
            q.add(str);
46
            visited.add(str);
47
          }
48
        }
49
      }
50
      level++;
51
    }
52

53
    return -1;
54
  }
55

56
  public String swapEle(String rem, int i, int j) {
57
    StringBuilder sb = new StringBuilder(rem);
58

59
    sb.setCharAt(i, rem.charAt(j));
60
    sb.setCharAt(j, rem.charAt(i));
61

62
    return sb.toString();
63
  }
64
}