Eight
| Time Limit: 1000MS | Memory Limit: 65536K | |||
| Total Submissions: 21880 | Accepted: 9674 | Special Judge | ||
Description
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:
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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 x
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:
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
5 6 7 8 5 6 7 8 5 6 7 8 5 6 7 8
9 x 10 12 9 10 x 12 9 10 11 12 9 10 11 12
13 14 11 15 13 14 11 15 13 14 x 15 13 14 15 x
r-> 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, and
frustrating 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 three
arrangement.
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
a row, where the tiles are represented by numbers 1 to 8, plus 'x'. For example, this puzzle
1 2 3 x 4 6 7 5 8
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.
string should include no spaces and start at the beginning of the line.
Sample Input
2 3 4 1 5 x 7 6 8
Sample Output
ullddrurdllurdruldr
Source
今天做了一下人人都是说是很经典的题目，poj1077Eight。。。
其实这道题目并不是很难。关键是在BFS时如何设置标志数组，如果是最容易想到的是vist[][][][][][][][][]设置一个九维数组。。。。
我一想到这个我就知道着一定超内存了。。。
其实一想也没有那么多的变化。。。
是9的全排列9！= 362 880种 。。
所以上网找资料就找到了康拓展开。。。。
我最记得是在2013广东省“有为杯”ACM程序大赛热身时有过这类题。。。
用康拓展开成hash函数。。。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int hash[363000];
int fact[9] = {1,1,2,6,24,120,720,5040,40320};
char finishPath[1001];
struct queue
{
int map[9];
int x_place;
char dir;
int last;
int hashvalue;
}queue[363000];
int m_hash(int m[])
{
int vist[10]={0},sum = 0,num;
for(int i=0;i<9;i++)
{
num = 0;
for(int j=1;j<m[i];j++)
if(vist[j] == 0)
num++;
vist[m[i]] = 1;
sum+=num*fact[8-i];
}
return sum;
}
int BFS()
{
int head = 0,tail = 1;
int s,q_map[9];
int q_x,q_hash,tem;
while(head < tail)
{
s = head++;
if(queue[s].hashvalue == 0)
return s;
for(int i=0;i<9;i++) //将map[]的 值先放入暂时数组q_map[]中
q_map[i] = queue[s].map[i];
q_x = queue[s].x_place-3; //用q_x保存 x 点上下左右的点
if(q_x>=0 && q_x < 9 ) //x 的上点
{
tem = q_map[queue[s].x_place];
q_map[queue[s].x_place] = q_map[q_x];
q_map[q_x] =tem;
q_hash = m_hash(q_map);
if(hash[q_hash] == 0)
{
for(int i=0;i<9;i++)
queue[tail].map[i] = q_map[i];
queue[tail].dir = 'u';
queue[tail].hashvalue = q_hash;
queue[tail].last = s;
queue[tail++].x_place = q_x;
hash[q_hash] = 1;
}
tem = q_map[queue[s].x_place];
q_map[queue[s].x_place] = q_map[q_x];
q_map[q_x] =tem;
}
q_x = queue[s].x_place-1;
if(q_x!=2 && q_x!=5 && q_x!=-1 ) // x 的左点
{
tem = q_map[queue[s].x_place];
q_map[queue[s].x_place] = q_map[q_x];
q_map[q_x] =tem;
q_hash = m_hash(q_map);
if(hash[q_hash] == 0)
{
for(int i=0;i<9;i++)
queue[tail].map[i] = q_map[i];
queue[tail].dir = 'l';
queue[tail].hashvalue = q_hash;
queue[tail].last = s;
queue[tail++].x_place = q_x;
hash[q_hash] = 1;
}
tem = q_map[queue[s].x_place];
q_map[queue[s].x_place] = q_map[q_x];
q_map[q_x] =tem;
}
q_x = queue[s].x_place+3;
if(q_x>=0 && q_x < 9 ) // x 的下点
{
tem = q_map[queue[s].x_place];
q_map[queue[s].x_place] = q_map[q_x];
q_map[q_x] =tem;
q_hash = m_hash(q_map);
if(hash[q_hash] == 0)
{
for(int i=0;i<9;i++)
queue[tail].map[i] = q_map[i];
queue[tail].dir = 'd';
queue[tail].hashvalue = q_hash;
queue[tail].last = s;
queue[tail++].x_place = q_x;
hash[q_hash] = 1;
}
tem = q_map[queue[s].x_place];
q_map[queue[s].x_place] = q_map[q_x];
q_map[q_x] =tem;
}
q_x = queue[s].x_place+1;
if(q_x!=3 && q_x!=6 && q_x!=9 ) // x 的右点
{
tem = q_map[queue[s].x_place];
q_map[queue[s].x_place] = q_map[q_x];
q_map[q_x] =tem;
q_hash = m_hash(q_map);
if(hash[q_hash] == 0)
{
for(int i=0;i<9;i++)
queue[tail].map[i] = q_map[i];
queue[tail].dir = 'r';
queue[tail].hashvalue = q_hash;
queue[tail].last = s;
queue[tail++].x_place = q_x;
hash[q_hash] = 1;
}
tem = q_map[queue[s].x_place];
q_map[queue[s].x_place] = q_map[q_x];
q_map[q_x] =tem;
}
} //while
return -1;
}
int main()
{
char ch[4];
for(int j=0;j<9;j++)
{
scanf("%s",ch);
if(ch[0]!='x')
queue[0].map[j] = ch[0]-'0';
else
{
queue[0].dir = '\0';
queue[0].last = -1;
queue[0].x_place = j;
queue[0].map[j] = 9;
}
}
queue[0].hashvalue = m_hash(queue[0].map);
hash[queue[0].hashvalue] = 1;
int Finish = BFS();
if(Finish != -1)
{
int F = Finish,t=0;
memset(finishPath,0,sizeof(finishPath));
while(queue[F].dir != '\0')
{
finishPath[t++] = queue[F].dir;
F = queue[F].last;
}
finishPath[t] = '\0';
for(t=t-1;t>=0;t--)
printf("%c",finishPath[t]);
printf("\n");
}
else
printf("unsolvable\n");
system("pause");
return 0;
}
不过可惜在杭电上超时~~~
因为杭电上是多组数据。。。
如果将上面的程序简单地改成多组输入将会超时。。。
所以需要用打表的方式来存会快很多。。。。
而且还要BFS的反向搜索。。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int hash[363000];
int mhash[363000]; //用来存哈希值时的对应的队列下标
int fact[9] = {1,1,2,6,24,120,720,5040,40320};
char finishPath[1001];
struct queue
{
int map[9];
int x_place;
char dir;
int last;
int hashvalue;
}queue[363000];
int m_hash(int m[])
{
int vist[10]={0},sum = 0,num;
for(int i=0;i<9;i++)
{
num = 0;
for(int j=1;j<m[i];j++)
if(vist[j] == 0)
num++;
vist[m[i]] = 1;
sum+=num*fact[8-i];
}
return sum;
}
void BFS()
{
int head = 0,tail = 1;
int s,q_map[9];
int q_x,q_hash,tem;
while(head < tail)
{
s = head++;
mhash[queue[s].hashvalue] = s;
for(int i=0;i<9;i++) //将map[]的 值先放入暂时数组q_map[]中
q_map[i] = queue[s].map[i];
q_x = queue[s].x_place-3; //用q_x保存 x 点上下左右的点
if(q_x>=0 && q_x < 9 ) //x 的上点
{
tem = q_map[queue[s].x_place];
q_map[queue[s].x_place] = q_map[q_x];
q_map[q_x] =tem;
q_hash = m_hash(q_map);
if(hash[q_hash] == 0)
{
for(int i=0;i<9;i++)
queue[tail].map[i] = q_map[i];
queue[tail].dir = 'd';
queue[tail].hashvalue = q_hash;
queue[tail].last = s;
queue[tail++].x_place = q_x;
hash[q_hash] = 1;
}
tem = q_map[queue[s].x_place];
q_map[queue[s].x_place] = q_map[q_x];
q_map[q_x] =tem;
}
q_x = queue[s].x_place-1;
if(q_x!=2 && q_x!=5 && q_x!=-1 ) // x 的左点
{
tem = q_map[queue[s].x_place];
q_map[queue[s].x_place] = q_map[q_x];
q_map[q_x] =tem;
q_hash = m_hash(q_map);
if(hash[q_hash] == 0)
{
for(int i=0;i<9;i++)
queue[tail].map[i] = q_map[i];
queue[tail].dir = 'r';
queue[tail].hashvalue = q_hash;
queue[tail].last = s;
queue[tail++].x_place = q_x;
hash[q_hash] = 1;
}
tem = q_map[queue[s].x_place];
q_map[queue[s].x_place] = q_map[q_x];
q_map[q_x] =tem;
}
q_x = queue[s].x_place+3;
if(q_x>=0 && q_x < 9 ) // x 的下点
{
tem = q_map[queue[s].x_place];
q_map[queue[s].x_place] = q_map[q_x];
q_map[q_x] =tem;
q_hash = m_hash(q_map);
if(hash[q_hash] == 0)
{
for(int i=0;i<9;i++)
queue[tail].map[i] = q_map[i];
queue[tail].dir = 'u';
queue[tail].hashvalue = q_hash;
queue[tail].last = s;
queue[tail++].x_place = q_x;
hash[q_hash] = 1;
}
tem = q_map[queue[s].x_place];
q_map[queue[s].x_place] = q_map[q_x];
q_map[q_x] =tem;
}
q_x = queue[s].x_place+1;
if(q_x!=3 && q_x!=6 && q_x!=9 ) // x 的右点
{
tem = q_map[queue[s].x_place];
q_map[queue[s].x_place] = q_map[q_x];
q_map[q_x] =tem;
q_hash = m_hash(q_map);
if(hash[q_hash] == 0)
{
for(int i=0;i<9;i++)
queue[tail].map[i] = q_map[i];
queue[tail].dir = 'l';
queue[tail].hashvalue = q_hash;
queue[tail].last = s;
queue[tail++].x_place = q_x;
hash[q_hash] = 1;
}
tem = q_map[queue[s].x_place];
q_map[queue[s].x_place] = q_map[q_x];
q_map[q_x] =tem;
}
} //while
}
int main()
{
for(int i=0;i<9;i++)
queue[0].map[i] = i+1;
queue[0].dir = '\0';
queue[0].last = -1;
queue[0].x_place = 8;
queue[0].hashvalue = 0;
memset(mhash,0,sizeof(mhash));
BFS();
char ch[4];
int mmap[10],hvalue;
while(scanf("%s",ch)!=EOF)
{
if(ch[0]!='x')
mmap[0] = ch[0]-'0';
else
mmap[0] = 9;
for(int j=1;j<9;j++)
{
scanf("%s",ch);
if(ch[0]!='x')
mmap[j] = ch[0]-'0';
else
mmap[j] = 9;
}
hvalue = m_hash(mmap);
if(hvalue != 0)
{
if(mhash[hvalue])
{
memset(finishPath,0,sizeof(finishPath));
int F = mhash[hvalue];
while(queue[F].dir != '\0')
{
printf("%c",queue[F].dir);
F = queue[F].last;
}
printf("\n");
}
else
printf("unsolvable\n");
}
else
printf("\n");
}
system("pause");
return 0;
}