八码数 状态压缩
- 状态压缩 将二维数组压缩为一维数组
int index = start.indexOf("x"); // 获取 x在一维数组坐标
int x = index / 3, y = index % 3; // 一维下标转二维
index = x * 3 + b; // 二维下标转一维
-
使用
HashMap
记录每个字符串 的移动次数 -
每移动一次, x变换一次位置, 距离dist + 1, 直到移动的目标字符串 到达末尾
Map<String, Integer> dist = new HashMap<>()
import java.util.*;
public class Main {
static int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
// 交换字符数组
// 字符串转为char数组, 对一维坐标进行转换
static void swap(char[] ch, int x, int y) {
char temp = ch[x];
ch[x] = ch[y];
ch[y] = temp;
}
static int bfs(String start) {
// 距离数组 记录每一个字符串(每移动一次) 距起点距离
Map<String, Integer> dist = new HashMap<>();
dist.put(start, 0); // 起点距离0
// 队列
Queue<String> queue = new LinkedList<>();
queue.offer(start);
// 终状态
String end = "12345678x";
// 循环队列
while(!queue.isEmpty()) {
start = queue.poll(); // 出队
int distance = dist.get(start); // 取出当前节点 距离
// 构成目标字符串 退出
if(start.equals(end))
return distance; // 返回距离
/*
* 转化为 二维数组坐标(字符转化为3*3矩阵)
*/
int index = start.indexOf("x"); // 获取 x在一维数组坐标
int x = index / 3, y = index % 3;
// 四个方向循环
for(int i = 0; i < 4; i++) {
int a = x + dx[i], b = y + dy[i];
if(a < 0 || b < 0 || a >= 3 || b >= 3) // 越界
continue;
char []ch = start.toCharArray();
// 交换位置 引用传递char
// a*3+b 二维坐标转一维坐标
swap(ch, index, a * 3 + b);
String str = new String(ch); // 构建转换后 字符串
// 距离数组为空, 该点未走过
if(dist.get(str) == null) {
queue.offer(str);
dist.put(str, distance + 1);
}
}
}
return -1;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String start = "";
for(int i = 0; i < 9; i++)
start += sc.next();
System.out.print(bfs(start));
}
}