题目描述
在一个3×3的网格中,1~8这8个数字和一个“X”恰好不重不漏地分布在这3×3的网格中。
例如:
1 2 3
X 4 6
7 5 8
在游戏过程中,可以把“X”与其上、下、左、右四个方向之一的数字交换(如果存在)。
我们的目的是通过交换,使得网格变为如下排列(称为正确排列):
1 2 3
4 5 6
7 8 X
例如,示例中图形就可以通过让“X”先后与右、下、右三个方向的数字交换成功得到正确排列。
交换过程如下:
1 2 3 1 2 3 1 2 3 1 2 3
X 4 6 4 X 6 4 5 6 4 5 6
7 5 8 7 5 8 7 X 8 7 8 X
把“X”与上下左右方向数字交换的行动记录为“u”、“d”、“l”、“r”。
现在,给你一个初始网格,请你通过最少的移动次数,得到正确排列。
输入格式
输入占一行,将3×3的初始网格描绘出来。
例如,如果初始网格如下所示:
1 2 3
x 4 6
7 5 8
则输入为:1 2 3 x 4 6 7 5 8
输出格式
输出占一行,包含一个字符串,表示得到正确排列的完整行动记录。如果答案不唯一,输出任意一种合法方案即可。
如果不存在解决方案,则输出”unsolvable”。
样例
2 3 4 1 5 x 7 6 8
输出
ullddrurdllurdruldr
算法1
(A*) $O(不会算)$
JAVA版本题解
时间复杂度
参考文献
JAVA 代码
import java.util.*;
public class Main {
public static int f(String state) {
int res = 0;
for (int i = 0; i < state.length(); i++) {
if (state.charAt(i) != 'x') {
int t = state.charAt(i) - '1';
res += Math.abs(t / 3 - i / 3) + Math.abs(t % 3 - i % 3);
}
}
return res;
}
public static String bfs(String start) {
int[] dx = {-1, 0, 1, 0};
int[] dy = {0, 1, 0, -1};
char[] ops = {'u', 'r', 'd', 'l'};
String end = "12345678x";
Map<String, Integer> dist = new HashMap<>();
Set<String> st = new HashSet<>();
Map<String, Node> prev = new HashMap<>();
PriorityQueue<Node> queue = new PriorityQueue<>(16, (o1, o2) -> o1.d - o2.d);
queue.offer(new Node(f(start), start));
dist.put(start, 0);
while (!queue.isEmpty()) {
Node node = queue.poll();
String state = node.state;
if (state.equals(end)) {
break;
}
if (st.contains(state)) continue;
st.add(state);
int x = 0, y = 0;
for (int i = 0; i < 9; i++) {
if (state.charAt(i) == 'x') {
x = i / 3;
y = i % 3;
break;
}
}
String source = state;
int step = dist.get(source);
for (int i = 0; i < 4; i++) {
int a = x + dx[i];
int b = y + dy[i];
if (a < 0 || a >= 3 || b < 0 || b >= 3) continue;
state = source;
StringBuffer sb = new StringBuffer();
for (int j = 0; j < 9; j++) {
if (j == 3 * x + y) {
sb.append(state.charAt(3 * a + b));
} else if (j == 3 * a + b) {
sb.append(state.charAt(3 * x + y));
} else {
sb.append(state.charAt(j));
}
}
state = sb.toString();
if (!dist.containsKey(state) || dist.get(state) > step + 1) {
dist.put(state, step + 1);
queue.offer(new Node(f(state) + dist.get(state), state));
prev.put(state, new Node(i, source));
}
}
}
StringBuffer res = new StringBuffer();
while (!end.equals(start)) {
Node node = prev.get(end);
int t = node.d;
char c = ops[t];
res.append(c);
end = node.state;
}
return res.reverse().toString();
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
String str = scan.nextLine();
String[] s = str.split(" ");
char[] seq = new char[s.length];
char[] g = new char[s.length];
for (int i = 0, j = 0; i < s.length; i++) {
g[i] = s[i].charAt(0);
if (g[i] != 'x') {
seq[j++] = g[i];
}
}
int t = 0;
for (int i = 0; i < 8; i++) {
for (int j = i + 1; j < 8; j++) {
if (seq[i] > seq[j]) {
t++;
}
}
}
if (t % 2 == 1) {
System.out.println("unsolvable");
return;
}
String gg = "";
for (char c : g) {
gg += c;
}
System.out.println(bfs(gg));
}
}
class Node {
int d;
String state;
public Node(int d, String state) {
this.d = d;
this.state = state;
}
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla