Eight
| Time Limit: 1000MS | Memory Limit: 65536K | |||
| Total Submissions: 30176 | Accepted: 13119 | 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:
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:
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.
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
is described by this list:
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.
Sample Input
2 3 4 1 5 x 7 6 8
Sample Output
ullddrurdllurdruldr
Source
题目链接：POJ 1077
主要就是用康托展开来映射判重的问题，info::val就是康托展开hash值，info::step就是积累的状态。另外感觉这题剧毒，自己本来用int vis[]和char his[]想最后回溯记录答案从而代替速度比较慢的string，结果居然超时……TLE一晚上，要不是看了大牛的博客估计要一直T在这个坑点上。还有不知道为什么string的加号重载在C++编译器里会CE，换G++才过。相比单组输入的POJ，多组输入的HDU就友好多了，打个表就可以水过了，双广、A*神马的写起来麻烦就先不写了……
什么是康托展开？——康托展开介绍文章
POJ代码：
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<sstream>
#include<cstring>
#include<bitset>
#include<cstdio>
#include<string>
#include<deque>
#include<stack>
#include<cmath>
#include<queue>
#include<set>
#include<map>
using namespace std;
#define INF 0x3f3f3f3f
#define CLR(x,y) memset(x,y,sizeof(x))
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 362880 + 20;
int fact[10] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
int direct[4][2] = {{ -1, 0}, {1, 0}, {0, -1}, {0, 1}};
char MOVE[5] = "udlr";
struct info
{
int s[9];
int indx;
string step;
int val;
};
info S, E;
int T;
int vis[N];
string ans;
int calcantor(int s[])
{
int r = 0;
for (int i = 0; i < 9; ++i)
{
int k = 0;
for (int j = i + 1; j < 9; ++j)
{
if (s[j] < s[i])
++k;
}
r = r + k * fact[8 - i];
}
return r;
}
bool check(const int &x, const int &y)
{
return (x >= 0 && x < 3 && y >= 0 && y < 3);
}
bool bfs()
{
CLR(vis, 0);
queue<info>Q;
Q.push(S);
vis[S.val] = 1;
info now, v;
while (!Q.empty())
{
now = Q.front();
Q.pop();
if (now.val == T)
{
ans = now.step;
return true;
}
for (int i = 0; i < 4; ++i)
{
int x = now.indx / 3;
int y = now.indx % 3;
x += direct[i][0];
y += direct[i][1];
if (check(x, y))
{
v = now;
v.indx = x * 3 + y;
v.s[now.indx] = v.s[v.indx];
v.s[v.indx] = 0;
v.val = calcantor(v.s);
if (!vis[v.val])
{
vis[v.val] = 1;
v.step = now.step + MOVE[i];
if (v.val == T)
{
ans = v.step;
return true;
}
Q.push(v);
}
}
}
}
return false;
}
int main(void)
{
char temp;
int i;
T = 46233;
while (cin >> temp)
{
if (temp == 'x')
{
S.s[0] = 0;
S.indx = 0;
}
else
S.s[0] = temp - '0';
for (i = 1; i < 9; ++i)
{
cin >> temp;
if (temp == 'x')
{
S.s[i] = 0;
S.indx = i;
}
else
S.s[i] = temp - '0';
}
S.val = calcantor(S.s);
puts(!bfs() ? "unsolvable" : ans.c_str());
}
return 0;
}
HDU代码：
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<sstream>
#include<cstring>
#include<bitset>
#include<cstdio>
#include<string>
#include<deque>
#include<stack>
#include<cmath>
#include<queue>
#include<set>
#include<map>
using namespace std;
#define INF 0x3f3f3f3f
#define CLR(x,y) memset(x,y,sizeof(x))
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 362880 + 10;
int fact[10] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
struct info
{
int s[9];
int indx;
string path;
int val;
void cal()
{
val = 0;
for (int i = 0; i < 9; ++i)
{
int k = 0;
for (int j = i + 1; j < 9; ++j)
{
if (s[j] < s[i])
++k;
}
val = val + k * fact[8 - i];
}
}
};
info init = {{1, 2, 3, 4, 5, 6, 7, 8, 9}, 8, "", 0}, S;
int direct[4][2] = {{ -1, 0}, {1, 0}, {0, -1}, {0, 1}}; //ÏÂÉÏÓÒ×ó
char MOV[5] = "durl";
string ans[N];
int vis[N];
void bfs()
{
CLR(vis, 0);
queue<info>Q;
info now, v;
Q.push(init);
vis[init.val] = 1;
ans[init.val] = init.path;
while (!Q.empty())
{
now = Q.front();
Q.pop();
for (int i = 0; i < 4; ++i) //ÏÂÉÏÓÒ×ó
{
int x = now.indx / 3;
int y = now.indx % 3;
x += direct[i][0];
y += direct[i][1];
if (x >= 0 && x < 3 && y >= 0 && y < 3)
{
v = now;
v.indx = x * 3 + y;
v.path = MOV[i] + now.path;
swap(v.s[v.indx], v.s[now.indx]);
v.cal();
if (!vis[v.val])
{
vis[v.val] = 1;
ans[v.val] = v.path;
Q.push(v);
}
}
}
}
}
int main(void)
{
char temp[5], i;
bfs();
while (~scanf("%s", temp))
{
S.path = "";
if (temp[0] == 'x')
{
S.s[0] = 9;
S.indx = 0;
}
else
S.s[0] = temp[0] - '0';
for (i = 1; i < 9; ++i)
{
scanf("%s", temp);
if (temp[0] == 'x')
{
S.s[i] = 9;
S.indx = i;
}
else
S.s[i] = temp[0] - '0';
}
S.cal();
puts(!vis[S.val] ? "unsolvable" : ans[S.val].c_str());
}
return 0;
}
最近学了下IDA*，发现速度贼快，比哈希的不知道高到哪里去了，自己整理了一下一般写法，感觉还是比较模版的，可以参考上一篇IDA*的伪代码，IDA*快到如果用BFS要打表的HDU上的数据可以直接在线搜索过了，确实比较快，这里需要加一个防止走回路的剪枝（有效减少无用搜索），否则可能会超时，当然一开始要判断一下是否输入序列是无解的，可以暂时把x忽略掉，然后算7个数的逆序数，逆序数偶数才有解，奇数直接输出unsolvable，具体原理可以百度一下
代码：
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <sstream>
#include <numeric>
#include <cstring>
#include <bitset>
#include <string>
#include <deque>
#include <stack>
#include <cmath>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 9;
int arr[N], T[N] = {1, 2, 3, 4, 5, 6, 7, 8, 0};
int Maxdep, top, stdpos[N] = {8, 0, 1, 2, 3, 4, 5, 6, 7};
char Ops[1010];
int dis(int cur, int ori)
{
int x = cur / 3, y = cur % 3;
return abs(x - ori / 3) + abs(y - ori % 3);
}
int Need(int A[])
{
int ret = 0;
for (int i = 0; i < N; ++i)
if (A[i] != T[i])
ret += dis(i, stdpos[A[i]]);
return ret;
}
inline bool check(int x, int y)
{
return x >= 0 && x < 3 && y >= 0 && y < 3;
}
int dfs(int dep, int Arr[], char pre)
{
int need = Need(Arr);
if (need == 0)
return 1;
else if (need + dep > Maxdep)
return 0;
else
{
int x, y, idx, i;
int Temp[N];
for (int i = 0; i < N; ++i)
{
if (Arr[i] == 0)
{
idx = i;
break;
}
}
x = idx / 3, y = idx % 3;
if (pre != 'u' && check(x + 1, y))
{
for (i = 0; i < N; ++i)
Temp[i] = Arr[i];
swap(Temp[(x + 1) * 3 + y], Temp[idx]);
Ops[top++] = 'd';
if (dfs(dep + 1, Temp, 'd'))
return 1;
else
--top;
}
if (pre != 'l' && check(x, y + 1))
{
for (i = 0; i < N; ++i)
Temp[i] = Arr[i];
swap(Temp[x * 3 + y + 1], Temp[idx]);
Ops[top++] = 'r';
if (dfs(dep + 1, Temp, 'r'))
return 1;
else
--top;
}
if (pre != 'd' && check(x - 1, y))
{
for (i = 0; i < N; ++i)
Temp[i] = Arr[i];
swap(Temp[(x - 1) * 3 + y], Temp[idx]);
Ops[top++] = 'u';
if (dfs(dep + 1, Temp, 'u'))
return 1;
else
--top;
}
if (pre != 'r' && check(x, y - 1))
{
for (i = 0; i < N; ++i)
Temp[i] = Arr[i];
swap(Temp[x * 3 + y - 1], Temp[idx]);
Ops[top++] = 'l';
if (dfs(dep + 1, Temp, 'l'))
return 1;
else
--top;
}
}
return 0;
}
int main(void)
{
char n[3];
int i, j, x;
while (~scanf("%s", n))
{
if (n[0] == 'x')
x = 0;
else
x = n[0] - '0';
arr[0] = x;
for (i = 1; i < 9; ++i)
{
scanf("%s", n);
if (n[0] == 'x')
x = 0;
else
x = n[0] - '0';
arr[i] = x;
}
int inv = 0;
for (i = 0; i < N; ++i)
{
if (arr[i] == 0)
continue;
for (j = i + 1; j < N; ++j)
{
if (arr[j] == 0)
continue;
if (arr[i] > arr[j])
++inv;
}
}
if (inv & 1)
puts("unsolvable");
else
{
top = 0;
Maxdep = 1;
while (!dfs(0, arr, -1))
++Maxdep;
Ops[top] = ' ';
puts(Ops);
}
}
return 0;
}