三阶平面魔方
有一个 3 × 3 的平面魔方，在平面魔方中，每个格子里分别无重复地写上 1 - 9 这 9 个数字。一共有 4 种对平面魔方的操作：
- 选择某一行左移。
- 选择某一行右移。
- 选择某一列上移。
- 选择某一列下移。
初始状态为：
123
456
789
比如选择第一行左移，魔方会变成下面这样：
231
456
789
现给出一个魔方状态，求还原到初始状态最少操作数
输入样例：
412
756
389
输出样例：
2
思路：
1、找出转动魔方形成的状态抽象为一个类Node，显然这个魔方是平面的，所以每次的状态都是一串 9位数的数字，例如：123456789
2、题目中要求最少操作次数，所以当翻转到已经操作过的状态的时候应该剔除，这个时候需要用到HashMap，我们将每次操作后的状态作为HashMap的key进行一次判断，如果不存在于HashMap中，就存入HashMap中，并且该key的value的值等于上一层状态加1。
3、需要注意的是在 rotate(Node now, int s, int d) 方法中，应该将传入的Node 对象进行深克隆，因为数组是引用类型，如果使用Node res = now，则会破坏同一层的每种状态的独立性。如何理解这个独立性，请看下图和分析：
0001.jpg
首先我们知道BFS是一层一层的往下搜索的，B、C、D都是由同一种状态转变过来的，A状态在转变的时候进行不同操作而产生了B、C、D这三种新状态，这三种状态不是同时产生的。如果我们在产生B的时候对A进行操作，修改了A，那么对于后面要产生C的时候，A已经不是原来的A了，那么对于C来说B修改了A就破坏了其这一层每种状态的独立性，所以我们应该将A克隆出来进行操作。
0002.jpg
代码：
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Scanner;
/**
* 三阶平面魔方
* @author 无处安身
*
*/
public class Main {
// 表示魔方产生的一种状态
static class Node implements Cloneable {
int[][] state = new int[3][3];
// 将魔方拼成一串数字 123456789
public int tonum() {
int res = 0;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
res = res * 10 + state[i][j];
}
}
return res;
}
@Override
protected Object clone() throws CloneNotSupportedException {
Node node = new Node();
node.state = new int[3][3];
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
node.state[i][j] = this.state[i][j];
}
}
return node;
}
}
public static void main(String[] args) throws CloneNotSupportedException {
Scanner sc = new Scanner(System.in);
// 处理输入
Node t = new Node();
for (int i = 0; i < 3; i++) {
String str = sc.nextLine();
int num = Integer.parseInt(str);
t.state[i][2] = num % 10;
num /= 10;
t.state[i][1] = num % 10;
num /= 10;
t.state[i][0] = num;
}
sc.close();
Queue<Node> q = new LinkedList<Node>();
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
q.add(t);
map.put(t.tonum(), 0);
Node now = t;
while(!q.isEmpty()) {
now = q.poll();
int tt = now.tonum();
// 如果成功完成魔方
if(tt == 123456789) {
System.out.println(map.get(123456789));
return;
}
Node next = null;
// 遍历3行 进行右移和左移操作，
for (int i = 0; i < 3; i++) {
// 进行一次翻转操作
next = rotate(now, i, -1);
// 如果map中不存在该状态
if(!map.containsKey(next.tonum())) {
int value = map.get(tt) + 1;
map.put(next.tonum(), value);
q.add(next);
}
next = rotate(now, i, 1);
if(!map.containsKey(next.tonum())) {
int value = map.get(tt) + 1;
map.put(next.tonum(), value);
q.add(next);
}
}
// 遍历3列 进行上移和下移操作，
for (int i = 0; i < 3; i++) {
next = rotate(now, i, -2);
if(!map.containsKey(next.tonum())) {
int value = map.get(tt) + 1;
map.put(next.tonum(), value);
q.add(next);
}
next = rotate(now, i, 2);
if(!map.containsKey(next.tonum())) {
int value = map.get(tt) + 1;
map.put(next.tonum(), value);
q.add(next);
}
}
}
// 无法还原魔方输出-1
System.out.println(-1);
}
public static Node rotate(Node next, int s, int d) throws CloneNotSupportedException {
Node res = (Node) next.clone();
if(d == -1) { // 右移
int temp = res.state[s][2];
res.state[s][2] = res.state[s][1];
res.state[s][1] = res.state[s][0];
res.state[s][0] = temp;
} else if(d == 1) { // 左移
int temp = res.state[s][0];
res.state[s][0] = res.state[s][1];
res.state[s][1] = res.state[s][2];
res.state[s][2] = temp;
} else if(d == -2) { // 上移
int temp = res.state[0][s];
res.state[0][s] = res.state[1][s];
res.state[1][s] = res.state[2][s];
res.state[2][s] = temp;
} else if(d == 2) { // 下移
int temp = res.state[2][s];
res.state[2][s] = res.state[1][s];
res.state[1][s] = res.state[0][s];
res.state[0][s] = temp;
}
return res;
}
}
网友评论