POJ 1077 Eight：八数码问题

POJ 1077 Eight：八数码问题2014-10-11 shuangde800 题目链接：

http://poj.org/problem？id=1077

题目类型：隐式图搜索

原题：

The 15-puzzle has been around for over 100 years; even if you don"t know it by that name, you"ve seen it. It is constructed with 15 sliding tiles, each with a number from 1 to 15 on it, and all packed into a 4 by 4 frame with one tile missing. Let"s call the missing tile "x"; the object of the puzzle is to arrange the tiles so that they are ordered as:

 123456789 10 11 12 13 14 15x

where the only legal operation is to exchange "x" with one of the tiles with which it shares an edge. As an example, the following sequence of moves solves a slightly scrambled puzzle:

 123412341234123456785678567856789x 10 129 10x 129 10 11 129 10 11 12 13 14 11 15 13 14 11 15 13 14x 15 13 14 15xr-> d-> r->

The letters in the previous row indicate which neighbor of the "x" tile is swapped with the "x" tile at each step; legal values are "r","l","u" and "d", for right, left, up, and down, respectively. Not all puzzles can be solved; in 1870, a man named Sam Loyd was famous for distributing an unsolvable version of the puzzle, andfrustrating many people. In fact, all you have to do to make a regular puzzle into an unsolvable one is to swap two tiles （not counting the missing "x" tile, of course）. In this problem, you will write a program for solving the less well-known 8-puzzle, composed of tiles on a three by threearrangement.

URL：http://www.bianceng.cn/Programming/sjjg/201410/45696.htm

Input

You will receive a description of a configuration of the 8 puzzle. The description is just a list of the tiles in their initial positions, with the rows listed from top to bottom, and the tiles listed from left to right within a row, where the tiles are represented by numbers 1 to 8, plus "x". For example, this puzzle

 123x46758

is described by this list:

 1 2 3 x 4 6 7 5 8

Output

You will print to standard output either the word ``unsolvable"", if the puzzle has no solution, or a string consisting entirely of the letters "r", "l", "u" and "d" that describes a series of moves that produce a solution. The string should include no spaces and start at the beginning of the line.

Sample Input

 23415x768

Sample Output

ullddrurdllurdruldr

题目大意：

编号为1～8的8个正方形被摆放成3行3列（留有一个格子为空），与空格相邻的编号格子可以移动到空格中。然后要求求出目标状态的方案。

分析与总结：

据说没做过八数码的人生是不完整的。看了lrj的书先做了这道，用到的是所有方法中最朴素，最简单的一种。直接单向bfs+哈希判重。

在poj上可以水过，但在HDU和ZOJ交就不行了。

在做这道题中学到的几样小技巧：

1. 数组直接用memcpy, memcmp对整块内存进行复制或者比较，速度比用for循环快。

2.用typedef来定义一个新名称可以更加方便。

3.哈希表与编码的应用

还有很多更好更高级的方法，我的人生还待完整……

#include<iostream>#include<cstring>#include<cstdio>#define MAXN 500000using namespace std;char input[30];int state[9], goal[9] = {1,2,3,4,5,6,7,8,0};int dir[4][2] = {{-1,0},{1,0},{0,-1},{0,1}}; // 上，下，左， 右char path_dir[5] = "udlr";int st[MAXN][9];int father[MAXN], path[MAXN]; // 保存打印路径const int MAXHASHSIZE = 1000003;int head[MAXHASHSIZE], next[MAXN];void init_lookup_table（） { memset（head, 0, sizeof（head））; }typedef int State[9];int hash（State& s） {int v = 0;for（int i = 0; i < 9; i++） v = v * 10 + s[i];return v % MAXHASHSIZE;}int try_to_insert（int s） {int h = hash（st[s]）;int u = head[h];while（u） {if（memcmp（st[u], st[s], sizeof（st[s]）） == 0） return 0;u = next[u];}next[s] = head[h];head[h] = s;return 1;}int bfs（）{init_lookup_table（）;father[0] = path[0] = -1;int front=0, rear=1;memcpy（st[0], state, sizeof（state））;while（front < rear）{int *s = st[front]; if（memcmp（s, goal, sizeof（goal））==0）{return front;}int j;for（j=0; j<9; ++j） if（！s[j]）break; // 找出0的位置int x=j/3, y=j%3; // 转换成行，列for（int i=0; i<4; ++i）{int dx = x+dir[i][0]; // 新状态的行，列int dy = y+dir[i][1];int pos = dx*3+dy;// 目标的位置if（dx>=0 && dx<3 && dy>=0 && dy<3）{int *newState = st[rear];memcpy（newState, s, sizeof（int）*9）;newState[j] = s[pos];newState[pos] = 0;if（try_to_insert（rear））{father[rear] = front;path[rear] = i;rear++;}}} front++;}return -1;}void print_path（int cur）{if（cur！=0）{print_path（father[cur]）;printf（"%c", path_dir[path[cur]]）;}}int main（）{while（gets（input））{// 转换成状态数组, "x"用0代替for（int pos=0, i=0; i<strlen（input）; ++i）{if（input[i]>="0" && input[i]<="9"）state[pos++] = input[i]-"0";else if（input[i]=="x"）state[pos++] = 0;}int ans;if（（ans=bfs（））！=-1）{ print_path（ans）;printf（"
"）;}}}