描述

在九宫格里放在1到8共8个数字还有一个是空格，与空格相邻的数字可以移动到空格的位置，问给定的状态最少需要几步能到达目标状态（用0表示空格）：
1 2 3
4 5 6
7 8 0

输入

输入一个给定的状态。

输出

输出到达目标状态的最小步数。不能到达时输出-1。

输入样例

1 2 3
4 0 6
7 5 8

输出样例

题解

#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(&current); // 计算当前数组的哈希值 
		
		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;
}