1、题目
image.png
2、分析
直接套用BFS的算法框架就可以。要注意“邻居”数组的定义方式和遍历方式
3、代码
class Solution {
//注意这里定义二维数组的方式
int[][] neighbors = {{1, 3}, {0, 2, 4}, {1, 5}, {0, 4}, {1, 3, 5}, {2, 4}};
public int slidingPuzzle(int[][] board) {
int m = 2, n = 3;
StringBuilder sb = new StringBuilder();
// 将矩阵转化为字符串
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
sb.append(board[i][j]);
}
}
// 设置 start target
String start = sb.toString();
String target = "123450";
Queue<String> q = new LinkedList<>();
Set<String> visited = new HashSet<>(); // 存储访问过的元素
q.offer(start);
visited.add(start);
int step = 0;
// 遍历每一层多叉树
while (!q.isEmpty()) {
int sz = q.size();
for (int i = 0; i < sz; i++) {
String cur = q.poll();
if (cur.equals(target)) return step; // 判断是否到达 target
int idx = cur.indexOf("0"); // 注意：找到数字0的索引
// 注意：遍历的数组的方式
for (int adj : neighbors[idx]) {
//找到邻居节点，然后交换
String newBoard = swap(cur, adj, idx);
if (!visited.contains(newBoard)) {
q.offer(newBoard);
visited.add(newBoard);
}
}
}
step++;
}
return -1;
}
// 交换位置
private String swap(String str, int dst, int src) {
char[] arr = str.toCharArray();
char temp = arr[src];
arr[src] = arr[dst];
arr[dst] = temp;
return new String(arr);
}
}
