描述
在九宫格里放在1到8共8个数字还有一个是空格,与空格相邻的数字可以移动到空格的位置,问给定的状态最少需要几步能到达目标状态(用0表示空格):
1 2 3
4 5 6
7 8 0
输入
输入一个给定的状态。
输出
输出到达目标状态的最小步数。不能到达时输出-1。
输入样例
1 2 3
4 0 6
7 5 8
输出样例
2
题解
#include <iostream>
#include <queue>
#include <cmath>
#include <cstring>
using namespace std;
// 哈希表
int mapx[362880];
int h[9] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320};
// 数组结构体,并记录0的位置信息,方便以后交换
typedef struct arr {
int num[3][3];
int zero_x, zero_y;
}arr;
arr start;
queue <arr> q;
void output(arr* x);
void left(arr* x);
void right(arr* x);
void up(arr* x);
void down(arr* x);
int rev(int a[3][3], int n); //求第n个位置的逆序数
int hashx(arr* x);
int bfs();
int main()
{
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
cin >> start.num[i][j];
// 结构体中的zero_x和zero_y用来记录0的位置
if (start.num[i][j] == 0)
{
start.zero_x = i;
start.zero_y = j;
}
}
}
memset(mapx, 0, sizeof(mapx));
// 将初值入队,并设定初值步长
q.push(start);
mapx[hashx(&start)] = 1;
cout << bfs() << endl;
}
void output(arr* x)
{
cout << "zero: " << x->zero_x << " " << x->zero_y << endl;
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
cout << x->num[i][j] << " ";
}
cout << endl;
}
cout << "step: " << mapx[hashx(x)] - 1 << endl << endl;
}
// 将0向左移动
void left(arr* x)
{
if (x->zero_y == 0)
return;
else
{
swap(x->num[x->zero_x][x->zero_y], x->num[x->zero_x][x->zero_y-1]);
x->zero_y -= 1;
}
}
// 将0向右移动
void right(arr* x)
{
if (x->zero_y == 2)
return;
else
{
swap(x->num[x->zero_x][x->zero_y], x->num[x->zero_x][x->zero_y+1]);
x->zero_y += 1;
}
}
// 将0向上移动
void up(arr* x)
{
if (x->zero_x == 0)
return;
else
{
swap(x->num[x->zero_x][x->zero_y], x->num[x->zero_x-1][x->zero_y]);
x->zero_x -= 1;
}
}
// 将0向下移动
void down(arr* x)
{
if (x->zero_x == 2)
return;
else
{
swap(x->num[x->zero_x][x->zero_y], x->num[x->zero_x+1][x->zero_y]);
x->zero_x += 1;
}
}
//求第n个位置的逆序数
int rev(int a[3][3], int n)
{
int x = a[n/3][n%3];
int re = 0;
while (n >= 0)
{
n--;
int row = n / 3;
int col = n % 3;
if (x < a[row][col])
re++;
}
return re;
}
// 求全排列的哈希值
int hashx(arr* x)
{
int pos = 0;
for (int i = 0; i < 9; i++)
{
pos += rev(x->num, i) * h[i];
}
printf("", &pos);
return pos;
}
int bfs()
{
// 当前数组 左移 右移 上移 下移
arr current, larr, rarr, uarr, darr;
int pos, last;
while (!q.empty())
{
if (mapx[322560] != 0)
{
return mapx[322560] - 1;
}
current = q.front();
q.pop();
last = hashx(¤t); // 计算当前数组的哈希值
larr = current;
left(&larr);
pos = hashx(&larr);
if (mapx[pos] == 0)
{
mapx[pos] = mapx[last] + 1;
q.push(larr);
// output(&larr);
}
rarr = current;
right(&rarr);
pos = hashx(&rarr);
if (mapx[pos] == 0)
{
mapx[pos] = mapx[last] + 1;
q.push(rarr);
// output(&rarr);
}
uarr = current;
up(&uarr);
pos = hashx(&uarr);
if (mapx[pos] == 0)
{
mapx[pos] = mapx[last] + 1;
q.push(uarr);
// output(&uarr);
}
darr = current;
down(&darr);
pos = hashx(&darr);
if (mapx[pos] == 0)
{
mapx[pos] = mapx[last] + 1;
q.push(darr);
// output(&darr);
}
}
return -1;
}