题目描述
在一个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
现在，给你一个初始网格，请你求出得到正确排列至少需要进行多少次交换。
输入格式
输入占一行，将3×3的初始网格描绘出来。
例如，如果初始网格如下所示：
1 2 3
x 4 6
7 5 8
则输入为：1 2 3 x 4 6 7 5 8
输出格式
输出占一行，包含一个整数，表示最少交换次数。
如果不存在解决方案，则输出”-1”。
输入样例：
2 3 4 1 5 x 7 6 8
输出样例
19
思路
对于八数码这道经典的bfs问题，之前就不止一次听说过了，但是到现在才真正的去解决了它😂。
其实这道题有好多种做法，像什么 朴素bfs + map 、双向bfs 、A* ....都能解决这道题。
但是由于我比较菜，所以暂时先贴 朴素bfs + map 的解法。
其实这题也不难，麻烦的主要就是两个点：
- 1、如何记录状态
- 2、如何记录当前变换到当前状态所需的最少交换次数
只要解决这两个问题，那这题其实就很简单了。
因为状态是一个个的3 x 3的矩阵，不太好存，所以我们能不能想到一个比较好存的方式来表示每个3 x 3的矩阵。动动脑袋瓜子想想=￣ω￣=。
我们可以把每个3 x 3的矩阵转化为一个字符串序列，比如：
1 2 3
x 4 6
7 5 8
我们可以把它转为123x46758，这样的话，我们状态表示就很轻松了。
那么还剩下一个问题，变换到当前状态的最小交换次数应该怎么存呢？
其实这里开个哈希表（C++对应unordered_map，java对应HashMap，python对应字典)就可以了。
既然现在两个问题都解决了，那么代码就很好写了=￣ω￣=
朴素版bfs + map
C++ 实现
#include <iostream>
#include <cstring>
#include <queue>
#include <unordered_map>
using namespace std;
unordered_map<string, int> dist;
int bfs(string start)
{
string end = "12345678x";
int dir[4][2] = { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
queue<string> q;
dist[start] = 0;
q.push(start);
while (q.size())
{
auto t = q.front();
q.pop();
if (t == end) return dist[t];
int distance = dist[t];
// 向四个方向扩展
for (int i = 0; i < 4; i ++ )
{
int cur = t.find('x');
// 获得 x 在 3 x 3 矩阵中的对应下标
int x = cur / 3, y = cur % 3;
int a = x + dir[i][0], b = y + dir[i][1];
if (a >= 0 && a < 3 && b >= 0 && b < 3)
{
// 交换对应位置的字符
swap(t[cur], t[a * 3 + b]);
if (!dist.count(t))
{
dist[t] = distance + 1;
q.push(t);
}
// 记得复原！！！
swap(t[cur], t[a * 3 + b]);
}
}
}
return -1;
}
int main()
{
string start;
for (int i = 0; i < 9; i ++ )
{
char s;
cin >> s;
start += s;
}
cout << bfs(start) << endl;
return 0;
}
Java实现
package cn.lwjppz.solution;
import java.io.*;
import java.util.*;
/**
* @author : lwj
* @since : 2021-02-08
*/
public class EightDigital {
static class Solution {
/**
* 标记状态是否访问过及到达此状态所需最短步数
*/
private Map<String, Integer> hash = new HashMap<>(1 << 3);
/**
* 方向数组
*/
private final int[][] dir = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
/**
* 初始状态
*/
private final String start;
public Solution(String start) {
this.start = start;
}
public String swap(String str, int source, int target) {
StringBuilder sb = new StringBuilder(str);
char ch = sb.charAt(source);
sb.replace(source, source + 1, String.valueOf(sb.charAt(target)));
sb.replace(target, target + 1, String.valueOf(ch));
return sb.toString();
}
public int bfs() {
Queue<String> q = new LinkedList<>();
q.offer(start);
hash.put(start, 0);
String end = "12345678x";
while (!q.isEmpty()) {
String t = q.poll();
if (end.compareTo(t) == 0) {
break;
}
for (int i = 0; i < 4; i++) {
int index = t.indexOf('x');
int x = index / 3 + dir[i][0], y = index % 3 + dir[i][1];
if (x >= 0 && x < 3 && y >= 0 && y < 3) {
int cur = x * 3 + y;
String curState = swap(t, index, cur);
if (hash.getOrDefault(curState, 0) == 0) {
hash.put(curState, hash.get(t) + 1);
q.offer(curState);
}
}
}
}
return hash.getOrDefault(end, -1);
}
}
static class Reader {
static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer tokenizer = new StringTokenizer("");
static String nextLine() throws IOException {
return reader.readLine();
}
static String next() throws IOException {
while (!tokenizer.hasMoreTokens()) {
tokenizer = new StringTokenizer(reader.readLine());
}
return tokenizer.nextToken();
}
static int nextInt() throws IOException {
return Integer.parseInt(next());
}
static double nextDouble() throws IOException {
return Double.parseDouble(next());
}
static void close() throws IOException {
reader.close();
}
}
public static void main(String[] args) throws IOException {
PrintWriter out = new PrintWriter(new PrintStream(System.out));
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 9; i++) {
sb.append(Reader.next());
}
Solution solution = new Solution(sb.toString());
int step = solution.bfs();
out.println(step);
out.flush();
}
}
题目链接：https://www.luogu.com.cn/problem/P1379，这题更简化
Q.E.D.
