八数码难题

Description

八数码问题也称为九宫问题。在3×3的棋盘上摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格(空格用0表示)，与空格相邻的棋子可以移到空格中。给出一个初始状态和一个目标状态，求出从初始状态转变成目标状态的移动棋子步数的最少值，以及棋盘移动的序列路径。初始状态如下： 目标状态如下：

要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。所谓问题的一个状态就是棋子在棋盘上的一种摆法。棋子移动后，状态就会发生改变。解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状态。

Input

共6行。前3行是初始游戏状态，后3行是目标游戏状态。

Output

输出第一行，初始状态到目标状态的最少步数 。 接下来若干行表示初始状态到目标状态在最小步数情况下的移动步骤。(每一行9个数字表示棋盘的一种状态)；特别地，如果初始状态无法到达输出-1

Sample Input

1 2 3 8 0 4 7 6 5 2 8 3 1 0 4 7 6 5

Sample Output

4 123804765 123084765 023184765 203184765 283104765

Solution

一道状态压缩的题目

将每个八数码的状态用一个９位数储存，然后直接搜索即可

注意每一次交换位置时９位数的变化为swap函数所示

Code

#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <algorithm>#include <cmath>#include <stack>#include <map>#include <vector>#include <queue>#define L 10000000#define LL long longusing namespace std;inline int gi() {  char cj = getchar();  int ans = 0, f = 1;  while (cj < '0' || cj > '9') {    if (cj == '-') f = -1;cj = getchar();  }  while (cj >= '0' && cj <= '9') ans = ans * 10 + cj - '0', cj = getchar();  return f * ans;}int be, en, x, posx, posy, head, tail = 1, bj = 0;int bfs[L], ans[L], a[L / 10], b[L / 10], PRe[L / 10];int f[10] = {0, 100000000, 10000000, 1000000, 100000, 10000, 1000, 100, 10, 1};int dx[4] = {0, 0, 1, -1}, dy[4] = {-1, 1, 0, 0};map <int, bool> vis;inline int swap(int num, int x, int y, int a, int b) {  int a1 = (x - 1) * 3 + y, b1 = (a - 1) * 3 + b;  int a2 = (num / f[a1]) % 10, b2 = (num / f[b1]) % 10;  return num - a2 * f[a1] - b2 * f[b1] + a2 * f[b1] + b2 * f[a1];}inline int exchangex(int x) {  if (x == 1 || x == 2 || x == 3) return 1;  if (x == 4 || x == 5 || x == 6) return 2;  if (x == 7 || x == 8 || x == 9) return 3;}inline int exchangey(int y) {  if (y == 1 || y == 4 || y == 7) return 1;  if (y == 2 || y == 5 || y == 8) return 2;  if (y == 3 || y == 6 || y == 9) return 3;}inline void print(int temp) {  if (pre[temp]) print(pre[temp]);  if (pre[temp] >= 0) printf("%09d/n", bfs[temp]);}int main() {  for (int i = 1; i <= 9; ++i) {    scanf("%1d", &x), be *= 10, be += x;    if (x == 0) posx = exchangex(i), posy = exchangey(i);  }  for (int i = 1; i <= 9; ++i) {scanf("%1d", &x), en *= 10, en += x;}  bfs[tail] = be, ans[tail] = 0, pre[tail] = 0, vis[be] = 1;  if (be == en) {printf("0"); return 0;}  a[tail] = posx, b[tail] = posy;  while (head <= tail) {    head++;    int x = bfs[head], y = ans[head], a1 = a[head], b1 = b[head];    for (int i = 0; i < 4; ++i) {      int a2 = a1 + dx[i], b2 = b1 + dy[i];      if (a2 > 0 && a2 <= 3 && b2 > 0 && b2 <= 3) {	int temp = swap(x, a2, b2, a1, b1);	if (!vis[temp]) {	  a[++tail] = a1 + dx[i], b[tail] = b1 + dy[i];	  vis[temp] = 1, bfs[tail] = temp, ans[tail] = y + 1, pre[tail] = head;	  if (bfs[tail] == en) {bj = 1; break;}	}      }    }    if (bj) break;  }  if (!bj) {printf("-1"); return 0;}  printf("%d/n", ans[tail]);  print(tail);  return 0;}
Summary
第一次提交的时候……爆空间，数组手滑又开大了
第二次提交发现搜索的顺序会影响输出的结果又调了很久搜索的顺序，按题目要求必须为：
int dx[4] = {0, 0, 1, -1}, dy[4] = {-1, 1, 0, 0};
另外记录是否访问过该状态的时候不能直接用bool数组，需要通过map定义，因为普通数组的下标不能达到9位数