广度优先搜索实现八数码 c++
时间: 2023-08-01 18:15:19 浏览: 46
好的,以下是广度优先搜索实现八数码的 C++ 代码:
```c++
#include <iostream>
#include <queue>
#include <map>
#include <vector>
#include <string>
using namespace std;
const int N = 3; // 3x3 的矩阵
struct Node
{
string state; // 当前状态
int step; // 当前步数
int x, y; // 空格的位置
bool operator<(const Node& t) const
{
return state < t.state;
}
};
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };
// 判断当前状态是否为目标状态
bool is_target(string state)
{
string target = "123456789";
target += '0' + N * N;
return state == target;
}
// 获取当前状态的下一步状态
vector<string> get_next_state(string state, int x, int y)
{
vector<string> res;
// 枚举空格的四个方向
for (int i = 0; i < 4; ++i)
{
int a = x + dx[i], b = y + dy[i];
if (a < 0 || a >= N || b < 0 || b >= N) continue;
swap(state[x * N + y], state[a * N + b]);
res.push_back(state);
swap(state[x * N + y], state[a * N + b]);
}
return res;
}
int bfs(string start)
{
queue<Node> q;
map<string, int> dist;
// 初始化起点
int x = 0, y = 0;
for (int i = 0; i < N * N; ++i)
if (start[i] == '0')
{
x = i / N, y = i % N;
break;
}
q.push({ start, 0, x, y });
dist[start] = 0;
while (!q.empty())
{
auto t = q.front();
q.pop();
if (is_target(t.state)) return t.step;
auto next_states = get_next_state(t.state, t.x, t.y);
for (auto& s : next_states)
if (!dist.count(s))
{
dist[s] = t.step + 1;
int x = 0, y = 0;
for (int i = 0; i < N * N; ++i)
if (s[i] == '0')
{
x = i / N, y = i % N;
break;
}
q.push({ s, t.step + 1, x, y });
}
}
return -1; // 无解
}
int main()
{
string start = "123456789";
start += '0' + N * N;
cout << bfs(start) << endl;
return 0;
}
```
该代码中,我们使用了 `struct Node` 表示状态,其中包含了当前状态的字符串表示 `state`、当前步数 `step`,以及空格的位置 `x`、`y`。
我们使用了 STL 中的 `queue` 表示队列,`map` 表示哈希表,`vector` 表示动态数组。
函数 `is_target` 判断当前状态是否为目标状态,函数 `get_next_state` 获取当前状态的下一步状态,函数 `bfs` 表示广度优先搜索算法。
在 `main` 函数中,我们定义了起点状态 `start`,并调用 `bfs` 函数进行搜索,最终输出结果。
需要注意的是,在本算法中,我们使用了哈希表 `map` 来判断当前状态是否已经访问过。同时,我们使用了 STL 中的 `swap` 函数来交换字符串中两个字符的位置。