---
title: "八数码"
created: 2025-11-28
tags:
  - 算法
---

# 八数码

## 8 题目 [八数码](https://www.acwing.com/problem/content/description/847/)

![[image-682f1305.png]]

## 思路分析

实际上就是暴力枚举 看x的位置 分别去看它的上下左右四个方向有哪些合法 如果合法就进行交换 然后以交换后的结果作为一个分支 继续进行接下来的交换操作

直到某个时候 与目标状态匹配 就成功了 如果最终所有操作都完成 还没达到目标状态 则表示不能达到

![[485-33a39445.png]]

起始状态： 为 1 2 3 x 4 6 7 5 8

交换一次：

x 与上方元素交换得到： x 2 3 1 4 6 7 5 8

x 与右方元素交换得到： 1 2 3 4 x 6 7 5 8

x 与下方元素交换得到： 1 2 3 7 4 6 x 5 8

交换两次得到：

2 x 3 1 4 6 7 5 8

1 x 3 4 2 6 7 5 8

1 2 3 4 6 x 7 5 8

1 2 3 4 5 6 7 x 8

1 2 3 7 4 6 5 x 8

交换三次得到：

2 3 x 1 4 6 7 5 8

.....

1 2 3 4 5 6 7 8 x

.....

得到了最终结果，输出 3.

问题主要在于  我们进行交换操作时是用二维数组的 而匹配时用一维的字符串要更方便

所以 关键就是 如何将二维和一维快速的进行转变

**一维坐标映射到二维 -> (x / n, x % n )**

**二维映射一维 -> x \* n + y**

然后 在bfs里面 我们要求每个状态距离起点状态的距离（步数） 而现在的状态是string 而非某个xy坐标 用不了st数组或者dist数组
所以 可以使用哈希表 直接以string为键 做距离数组

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

string s;

unordered_map<string,int> dist;

queue<string> q;

int dx[]={-1,0,1,0};

int dy[]={0,1,0,-1};

bool isVaild(int x,int y){

	return x>=0 && x<=2 && y>=0 && y<=2;

}

void bfs(string s){

	dist[s]=0;

	q.push(s);

	while(!q.empty()){

		string cur=q.front();q.pop();

		if(cur=="12345678x"){

			cout<<dist[cur]<<endl;

			return;

		}

		int pos=cur.find('x');

		int ux=pos/3,uy=pos%3;

		int last=dist[cur];

		for(int i=0;i<4;i++){

			int nx=ux+dx[i],ny=uy+dy[i];

			if(isVaild(nx,ny)){

				swap(cur[pos],cur[3*nx+ny]);

				if(dist.find(cur)==dist.end()){//若存在 mp.find(x)!=mp.end() 不存在则反之为==

					dist[cur]=last+1;

					q.push(cur);

				}

				swap(cur[pos],cur[3*nx+ny]);//还原现场

			}

		}

	}

	cout<<-1<<endl;

	return;

}

int main()

{

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	for(int i=1;i<=9;i++){

		char c; cin>>c;

		s+=c;

	}

	bfs(s);

	return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[搜索图论|搜索图论]] 🏠 [[00-冲刺国赛]] ➡️ [[魔板|魔板]]