LeetCode Solutions

			

class Solution {
 public:
  int slidingPuzzle(vector<vector<int>>& board) {
    constexpr int m = 2;
    constexpr int n = 3;
    const vector<int> dirs{0, 1, 0, -1, 0};
    const string goal = "123450";
    int steps = 0;
    string start;

    // Hash 2D vector to 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 (int k = 0; k < 4; ++k) {
          const int x = i + dirs[k];
          const int y = j + dirs[k + 1];
          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.count(s)) {
            q.push(s);
            seen.insert(s);
          }
          swap(s[zeroIndex], s[swappedIndex]);
        }
      }
    }

    return -1;
  }
};

			

class Solution {
  public int slidingPuzzle(int[][] board) {
    final int m = 2;
    final int n = 3;
    final int[] dirs = {0, 1, 0, -1, 0};
    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 k = 0; k < 4; ++k) {
          final int x = i + dirs[k];
          final int y = j + dirs[k + 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;
  }
}