八数码难题
2024年12月25日大约 2 分钟
广搜 1(数字上操作)
#include <bits/stdc++.h>
using namespace std;
int n;
int ten[10];
map<int, int> dis;
queue<int> q;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
ten[0] = 1;
for (int i = 1; i <= 8; i++)
ten[i] = ten[i - 1] * 10;
q.push(n);
dis[n] = 0;
while (!q.empty() &&
dis.find(123804765) == dis.end())
{
int now = q.front();
q.pop();
// 0 的位置、目标的位置
int pos = -1, t;
for (int i = 0; i <= 8; i++)
if (now / ten[i] % 10 == 0)
{
pos = i;
break;
}
// 上下左右
for (int i = 1; i <= 4; i++)
{
if (i == 1)
t = pos - 3;
if (i == 2)
t = pos + 3;
if (i == 3)
{
if (pos % 3 == 0)
t = -1;
else
t = pos - 1;
}
if (i == 4)
{
if (pos % 3 == 2)
t = -1;
else
t = pos + 1;
}
if (0 <= t && t <= 8)
{
// pos 上是 0,t 上是 x
int x = now / ten[t] % 10;
int nxt = now - x * ten[t] + x * ten[pos];
if (dis.find(nxt) == dis.end())
{
dis[nxt] = dis[now] + 1;
q.push(nxt);
}
}
}
}
cout << dis[123804765];
return 0;
}
广搜 2(真的展开九宫格)
#include <bits/stdc++.h>
using namespace std;
const int ed = 123804765;
map<int, int> dis;
queue<int> q;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int st;
cin >> st;
q.push(st);
dis[st] = 1;
while (!q.empty() && dis[ed] == 0)
{
int now = q.front();
q.pop();
/*
d[0][0] d[0][1] d[0][2]
d[1][0] d[1][1] d[1][2]
d[2][0] d[2][1] d[2][2]
*/
int d[3][3];
d[0][0] = now / 100000000 % 10;
d[0][1] = now / 10000000 % 10;
d[0][2] = now / 1000000 % 10;
d[1][0] = now / 100000 % 10;
d[1][1] = now / 10000 % 10;
d[1][2] = now / 1000 % 10;
d[2][0] = now / 100 % 10;
d[2][1] = now / 10 % 10;
d[2][2] = now / 1 % 10;
int x, y;
for (int i = 0; i <= 2; i++)
for (int j = 0; j <= 2; j++)
if (d[i][j] == 0)
x = i, y = j;
if (x != 0)
{
swap(d[x][y], d[x - 1][y]);
int nxt = 0;
for (int i = 0; i <= 2; i++)
for (int j = 0; j <= 2; j++)
nxt = nxt * 10 + d[i][j];
if (dis[nxt] == 0)
{
dis[nxt] = dis[now] + 1;
q.push(nxt);
}
swap(d[x][y], d[x - 1][y]);
}
if (x != 2)
{
swap(d[x][y], d[x + 1][y]);
int nxt = 0;
for (int i = 0; i <= 2; i++)
for (int j = 0; j <= 2; j++)
nxt = nxt * 10 + d[i][j];
if (dis[nxt] == 0)
{
dis[nxt] = dis[now] + 1;
q.push(nxt);
}
swap(d[x][y], d[x + 1][y]);
}
if (y != 0)
{
swap(d[x][y], d[x][y - 1]);
int nxt = 0;
for (int i = 0; i <= 2; i++)
for (int j = 0; j <= 2; j++)
nxt = nxt * 10 + d[i][j];
if (dis[nxt] == 0)
{
dis[nxt] = dis[now] + 1;
q.push(nxt);
}
swap(d[x][y], d[x][y - 1]);
}
if (y != 2)
{
swap(d[x][y], d[x][y + 1]);
int nxt = 0;
for (int i = 0; i <= 2; i++)
for (int j = 0; j <= 2; j++)
nxt = nxt * 10 + d[i][j];
if (dis[nxt] == 0)
{
dis[nxt] = dis[now] + 1;
q.push(nxt);
}
swap(d[x][y], d[x][y + 1]);
}
}
cout << dis[ed] - 1;
return 0;
}