https://www.cnblogs.com/grandyang/p/8955735.html
On a 2x3
board, there are 5 tiles represented by the integers 1 through 5, and an empty square represented by 0.
A move consists of choosing
0 and a 4-directionally adjacent number and swapping it.
The state of the board is solved if and only if the
board is [[1,2,3],[4,5,0]].
Given a puzzle board, return the least number of moves required so that the state of the board is solved. If it is impossible for the state of the board to be solved, return -1.
Examples:
Input: board = [[1,2,3],[4,0,5]] Output: 1 Explanation: Swap the 0 and the 5 in one move.
Input: board = [[1,2,3],[5,4,0]] Output: -1 Explanation: No number of moves will make the board solved.
Input: board = [[4,1,2],[5,0,3]] Output: 5 Explanation: 5 is the smallest number of moves that solves the board. An example path: After move 0: [[4,1,2],[5,0,3]] After move 1: [[4,1,2],[0,5,3]] After move 2: [[0,1,2],[4,5,3]] After move 3: [[1,0,2],[4,5,3]] After move 4: [[1,2,0],[4,5,3]] After move 5: [[1,2,3],[4,5,0]]
Input: board = [[3,2,4],[1,5,0]] Output: 14
Note:
boardwill be a 2 x 3 array as described above.board[i][j]will be a permutation of[0, 1, 2, 3, 4, 5].
https://leetcode.com/problems/sliding-puzzle/discuss/146652/Java-8ms-BFS-with-algorithm-explained
Consider each state in the board as a graph node, we just need to find out the min distance between start node and final target node "123450". Since it's a single point to single point questions, Dijkstra is not needed here. We can simply use BFS, and also count the level we passed. Every time we swap 0 position in the String to find the next state. Use a hashTable to store the visited states.
public int slidingPuzzle(int[][] board) {
String target = "123450";
String start = "";
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
start += board[i][j];
}
}
HashSet<String> visited = new HashSet<>();
// all the positions 0 can be swapped to
int[][] dirs = new int[][] { { 1, 3 }, { 0, 2, 4 },
{ 1, 5 }, { 0, 4 }, { 1, 3, 5 }, { 2, 4 } };
Queue<String> queue = new LinkedList<>();
queue.offer(start);
visited.add(start);
int res = 0;
while (!queue.isEmpty()) {
// level count, has to use size control here, otherwise not needed
int size = queue.size();
for (int i = 0; i < size; i++) {
String cur = queue.poll();
if (cur.equals(target)) {
return res;
}
int zero = cur.indexOf('0');
// swap if possible
for (int dir : dirs[zero]) {
String next = swap(cur, zero, dir);
if (visited.contains(next)) {
continue;
}
visited.add(next);
queue.offer(next);
}
}
res++;
}
return -1;
}
private String swap(String str, int i, int j) {
StringBuilder sb = new StringBuilder(str);
sb.setCharAt(i, str.charAt(j));
sb.setCharAt(j, str.charAt(i));
return sb.toString();
}
Convert array to string, e.g., [[1,2,3],[4,0,5]] -> "123405", hence the corresponding potential swap displacements are: -1, 1, -3, 3. Also note, charAt(2) and charAt(3) are not adjacent in original 2 dimensional int array and therefore are not valid swaps.
private static final int[] d = { 1, -1, 3, -3 }; // potential swap displacements.
public int slidingPuzzle(int[][] board) {
// convert board to string - initial state.
String s = Arrays.deepToString(board).replaceAll("\\[|\\]|,|\\s", "");
Queue<String> q = new LinkedList<>(Arrays.asList(s)); // add initial state to queue.
Set<String> seen = new HashSet<>(q); // used to avoid duplicates
int ans = 0; // record the # of rounds of Breadth Search
while (!q.isEmpty()) { // Not traverse all states yet?
// loop used to control search breadth.
for (int sz = q.size(); sz > 0; --sz) {
String str = q.poll();
if (str.equals("123450")) { return ans; } // found target.
int i = str.indexOf('0'); // locate '0'
for (int k = 0; k < 4; ++k) { // traverse all options.
int j = i + d[k]; // potential swap index.
// conditional used to avoid invalid swaps.
if (j < 0 || j > 5 || i == 2 && j == 3 || i == 3 && j == 2) { continue; }
char[] ch = str.toCharArray();
// swap ch[i] and ch[j]: ch[i] = ch[j], ch[j] = '0'. Updated per @caowang888's suggestion.
ch[i] = ch[j];
ch[j] = '0';
s = String.valueOf(ch); // a new candidate state.
if (seen.add(s)) { q.offer(s); } //Avoid duplicate.
}
}
++ans; // finished a round of Breadth Search, plus 1.
}
return -1;
}
Analysis:
There are at most 6! permutation of the 6 numbers: 0~5. For each permustion, cost spaceO(6); String.indexOf() and String.equals() cost time O(6). Therefore, space and time both cost 6 * 6! = 4320.
There are at most 6! permutation of the 6 numbers: 0~5. For each permustion, cost spaceO(6); String.indexOf() and String.equals() cost time O(6). Therefore, space and time both cost 6 * 6! = 4320.
Time & space: O(4320).
Feel free to let me know if you can find a tighter bound.
Update:
2
Question: Can you explain how did u determine the potential swap distance?
2
Question: Can you explain how did u determine the potential swap distance?
Answer:
When you map a 2 dimensional ( row * column ) matrix to 1 dimensional array, the swap to left and right are still -1 and 1 respectively in terms of index change in 1-D array. In contrast, the swap to up and down are -column and column as of index change.
That is, for any given index (i, j) in the matrix, it will be mapped to (i * column + j) in the array. Since in the matrix (i, j) could swap with (i, j - 1), (i, j + 1), (i - 1, j), and (i + 1, j), in the array (i * column + j) would swap with (i * column + j - 1), (i * column + j + 1), ((i - 1) * column + j) and ((i + 1) * column + j) accordingly.
We can easily conclude the swap displacement are -1, 1, -column, and column correspondingly.
e.g.: Let's consider (1, 2) in the following 3 * 5 matrix
column # --> 0 1 2 3 4
0 (0,0) (0,1) (0,2) (0,3) (0,4)
1 (1,0) (1,1) (1,2) (1,3) (1,4)
2 (2,0) (2,1) (2,2) (2,3) (2,4)
we can swap (1, 2) with (1, 1), (1, 3), (0, 2), and (2, 2)
When mapped to 1 dimensional array, it can be obtained that (1 * 5 + 2) swap with (1 * 5 + 2 - 1), (1 * 5 + 2 + 1), ((1 - 1) * 5 + 2) and ((1 + 1) * 5 + 2):
0 1 2 3 4 5 6 7 8 9 10 11 12 13
(0,0)(0,1)(0,2)(0,3)(0,4)(1,0)(1,1)(1,2)(1,3)(1,4)(2,0)(2,1)(2,2)(2,3)
14
(2,4)
Obviously, we can swap 7 with, 6 (= 7 - 1), 8 (= 7 + 1), 2 (= 7 - 5), 12 (= 7 + 5), where 5 is matrix column (width).
The displacements in the above case are -1, 1, -5, and 5.
http://www.noteanddata.com/leetcode-773-Sliding-Puzzle-java-solution-note.htmlpublic int slidingPuzzle(int[][] board) { StringBuilder sb = new StringBuilder(); for(int i = 0; i < board.length; ++i) { for(int j = 0; j < board[i].length; ++j) { sb.append(board[i][j]); } } String init = sb.toString(); Queue<String> queue = new LinkedList<>(); queue.add(init); Set<String> visited = new HashSet<>(); visited.add(init); /* index map [0,1,2], [3,4,5] */ int[][] dirs = { {1,3}, // 0 can to 1 and 3 {0,2,4}, {1,5}, {0,4}, {1,3,5}, {2,4} }; int steps = 0; while(!queue.isEmpty()) { Queue<String> nextQueue = new LinkedList<>(); while(!queue.isEmpty()) { String cur = queue.poll(); if("123450".equals(cur)) { return steps; } int zeroIndex = cur.indexOf('0'); for(int nextIndex: dirs[zeroIndex]) { char[] arr = cur.toCharArray(); arr[zeroIndex] = arr[nextIndex]; arr[nextIndex] = '0'; String next = new String(arr); if(!visited.contains(next)) { nextQueue.add(next); visited.add(next); } } } queue = nextQueue; steps++; } return -1; }
这个就是大家都玩过的滑块游戏，有个0表示空格，每次可以把这个空格和其他的一个相邻的位置进行交换。问最后能不能出现第一排第二排依次是"123450"的结局。如果不能，则返回-1；如果可以，需要返回所需要的最少步数。
Hard题目真的是一个比一个看起来难，但是只要有充足的经验，能看出这个是考BFS的题目，那么剩下的时间就是套用模板了吧。。
每次移动都相当于得到了一个新的状态，同时记录得到这个状态需要的步数，并把这个状态保存到已经出现过的set里。所以，本题的难点在于使用如果把二维数组和字符串进行转化的问题，代码写的很清楚了，就不详细说了。
需要注意的是，通过二维坐标得到字符串索引的方式是x * cols + y，我觉得应该是常识，可是我第一次没想出来。
Ps，吐槽一句，python的字符画不支持直接指定某个位置的字符，因此这个题里面迫不得已用了几次string和list互转的过程。。
最坏情况下的时间复杂度是O((MN)!)，空间复杂度是O(MN)。M,N代表行列数，这个题分别为2，3.
看到这道题不禁让博主想起了文曲星上的游戏-华容道，好吧，又暴露年龄了|||-.-，貌似文曲星这种电子辞典神马的已经是很古老的东西了，但是上面的一些经典游戏，什么英雄坛说啊，华容道啊，虽然像素分辨率低的可怜，画面效果连小霸王学习机其乐无穷都比不上，更不要说跟现在的什么撸啊撸，吃鸡之类的画面相比了，但是却给初高中时代的博主学习之余带来了无限的乐趣。不过这题跟华容道还是有些不同的，因为那个游戏各块的大小不同，而这道题的拼图大小都是一样的。那么像这种类似迷宫遍历的问题，又要求最小值的问题，要有强烈的BFS的感觉，没错，这道题正是用BFS来解的。这道题好就好在限定了棋盘的大小，是2x3的，这就让题目简单了许多，由于0的位置只有6个，我们可以列举出所有其下一步可能移动到的位置。为了知道每次移动后拼图是否已经恢复了正确的位置，我们肯定需要用个常量表示出正确位置以作为比较，那么对于这个正确的位置，我们还用二维数组表示吗？也不是不行，但我们可以更加简洁一些，就用一个字符串 "123450"来表示就行了，注意这里我们是把第二行直接拼接到第一行后面的，数字3和4起始并不是相连的。好，下面来看0在不同位置上能去的地方，字符串长度为6，则其坐标为 012345，转回二维数组为：
0 1 2 3 4 5
那么当0在位置0时，其可以移动到右边和下边，即{1, 3}位置；在位置1时，其可以移动到左边，右边和下边，即{0, 2, 4}位置；在位置2时，其可以移动到左边和下边，即{1, 5}位置；在位置3时，其可以移动到上边和右边，即{0, 4}位置；在位置4时，其可以移动到左边，右边和上边，即{1, 3, 5}位置；在位置5时，其可以移动到上边和左边，即{2, 4}位置。
然后就是标准的BFS的流程了，使用一个HashSet来记录访问过的状态，将初始状态start放入，使用一个queue开始遍历，将初始状态start放入。然后就是按层遍历，取出队首状态，先和target比较，相同就直接返回步数，否则就找出当前状态中0的位置，到dirs中去找下一个能去的位置，赋值一个临时变量cand，去交换0和其下一个位置，生成一个新的状态，如果这个状态不在visited中，则加入visited，并且压入队列queue，步数自增1。如果while循环退出后都没有回到正确状态，则返回-1，参见代码如下：
int slidingPuzzle(vector<vector<int>>& board) { int res = 0, m = board.size(), n = board[0].size(); string target = "123450", start = ""; vector<vector<int>> dirs{{1,3}, {0,2,4}, {1,5}, {0,4}, {1,3,5}, {2,4}}; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { start += to_string(board[i][j]); } } unordered_set<string> visited{start}; queue<string> q{{start}}; while (!q.empty()) { for (int i = q.size() - 1; i >= 0; --i) { string cur = q.front(); q.pop(); if (cur == target) return res; int zero_idx = cur.find("0"); for (int dir : dirs[zero_idx]) { string cand = cur; swap(cand[dir], cand[zero_idx]); if (visited.count(cand)) continue; visited.insert(cand); q.push(cand); } } ++res; } return -1; }
上面的解法虽然很炫，但是有局限性，比如若棋盘很大的话，难道我们还手动列出所有0能去的位置么？其实我们可以使用最普通的BFS遍历方式，就检查上下左右四个方向，那么这样我们就不能压缩二维数组成一个字符串了，我们visited数组中只能放二维数组了，同样的，queue 中也只能放二维数组，由于二维数组要找0的位置的话，还需要遍历，为了节省遍历时间，我们将0的位置也放入queue中，那么queue中的放的就是一个pair对儿，保存当前状态，已经0的位置，初始时将棋盘以及0的位置排入queue中。之后的操作就跟之前的解法没啥区别了，只不过这里我们的心位置就是上下左右，如果未越界的话，那么和0交换位置，看新状态是否已经出现过，如果这个状态不在visited中，则加入visited，并且压入队列queue，步数自增1。如果while循环退出后都没有回到正确状态，则返回-1，参见代码如下：
int slidingPuzzle(vector<vector<int>>& board) { int res = 0; set<vector<vector<int>>> visited; queue<pair<vector<vector<int>>, vector<int>>> q; vector<vector<int>> correct{{1, 2, 3}, {4, 5, 0}}; vector<vector<int>> dirs{{0, -1}, {-1, 0}, {0, 1}, {1, 0}}; for (int i = 0; i < 2; ++i) { for (int j = 0; j < 3; ++j) { if (board[i][j] == 0) q.push({board, {i, j}}); } } while (!q.empty()) { for (int i = q.size() - 1; i >= 0; --i) { auto t = q.front().first; auto zero = q.front().second; q.pop(); if (t == correct) return res; visited.insert(t); for (auto dir : dirs) { int x = zero[0] + dir[0], y = zero[1] + dir[1]; if (x < 0 || x >= 2 || y < 0 || y >= 3) continue; vector<vector<int>> cand = t; swap(cand[zero[0]][zero[1]], cand[x][y]); if (visited.count(cand)) continue; q.push({cand, {x, y}}); } } ++res; } return -1; }
X. Videos
花花酱 LeetCode 773. Sliding Puzzle - 刷题找工作 EP167
