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.
InputYou will receive, several descriptions of configuration of the 8 puzzle. One 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
1 2 3
x 4 6
7 5 8
is described by this list:
1 2 3 x 4 6 7 5 8
OutputYou 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. Do not print a blank line between cases.
Sample Input
2 3 4 1 5 x 7 6 8
Sample Output
ullddrurdllurdruldr 题意：给出8个数和一个空位（x表示），空位可以向四个方向和数交换，求最小的操作方式试其变成 （1 2 3 4 5 6 7 8 x）
思路：奇数码问题，先判断是否有解，因为是奇数码，所以有解的情况是两个情况的逆序对奇偶相同。
另外，可以把x置换成9，然后对这个9位数进行标记，可以用map<int,int>,也可以用康托展开将其和自然数一一对应。
A*的评估函数是每个位置到其应当位置的曼哈顿距离 A* + map + string路径记录：
#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<string.h>
#include<map>
using namespace std; struct Node
{
int cost,status;
int s[];
int pos;
int f;
string ans;
Node(int co=,int st=,int pos=,int f=,string ans=""):cost(co),status(st),pos(pos),f(f),ans(ans) {}
bool operator <(const Node x)const
{
return cost > x.cost;
}
};
map<int,int>mp;
int ways[][] = {,,-,,,,,-};
char WAYS[] = {'d','u','r','l'};
int ending;
Node start;
string ans;
int Merge(int *a,int l,int r)
{
int mid = (r+l)>>;
int i=l,j=mid+;
int b[r-l+];
int cnt = ;
int k = ;
while(i <= mid && j <= r)
{
if(a[i] <= a[j])
{
b[cnt++] = a[i++];
}
else
{
b[cnt++] = a[j++];
k += mid - i + ;
}
}
while(i <= mid)
b[cnt++] = a[i++];
while(j <= r)
b[cnt++] = a[j++];
for(int i=; i<cnt; i++)
{
a[l++] = b[i];
}
return k;
} void MER(int *a,int l,int r,int &cnt)
{
if(l >= r)
return;
int mid = (l+r)>>;
MER(a,l,mid,cnt);
MER(a,mid+,r,cnt);
cnt += Merge(a,l,r);
} int turn(int s[])
{
int cnt = ;
for(int i=; i<=; i++)
{
cnt *= ;
cnt += s[i];
}
return cnt;
} int init(char word[])
{
int a[];
for(int i=; i<=; i++)
scanf(" %c",&word[i]);
int cnt = ;
for(int i=; i<=; i++)
if((word[i]) != 'x')
a[++cnt] = word[i]-'';
int num = ;
MER(a,,cnt,num);
ending = ;
for(int i=; i<=; i++)
{
ending *= ;
ending += i;
if(word[i] == 'x')
start.s[i] = ,start.pos = i;
else
start.s[i] = word[i] - '';
}
return (num & ) == ;
} int cal(int s[])
{
int cnt = ;
for(int i=; i<=; i++)
{
if(s[i] == )
continue;
int x=(i-)/+,y=(i-)%+;
int xx=(s[i]-)/+,yy=(s[i]-)%+;
cnt += abs(x-xx)+abs(y-yy);
}
return cnt;
} bool A_bfs(Node start)
{
priority_queue<Node>que;
while(!que.empty())
que.pop();
start.status = turn(start.s);
start.f = cal(start.s);
start.cost = start.f;
que.push(start);
while(!que.empty())
{
Node tmp = que.top();
que.pop();
int status = tmp.status;
int cost = tmp.cost - tmp.f;
if(mp[status])
continue;
mp[status] = ;
if(status == ending)
{
ans = tmp.ans;
return ;
};
int x = (tmp.pos-)/+;
int y = (tmp.pos-)%+;
for(int i=; i<; i++)
{
int xx = x+ways[i][];
int yy = y+ways[i][];
if(xx < || xx > || yy < || yy > )
continue;
Node t = tmp;
t.s[(x-)*+y] = tmp.s[(xx-)*+yy];
t.s[(xx-)*+yy] = ;
t.status = turn(t.s);
t.f = cal(t.s);
t.cost = cost++t.f;
t.pos = (xx-)*+yy;
t.ans += WAYS[i];
que.push(t);
} }
return ;
} int main()
{
char word[];
while(~scanf(" %c",&word[]))
{
mp.clear();
if(init(word))
printf("unsolvable\n");
else
{
A_bfs(start);
cout << ans << endl;
}
}
}
双向bfs+康拓展开+递归路径记录（注：路径记录不能都用递归，会ME，也许姿势不对，对于从终态搜索的，因为其本身就是倒序，可以采用递推，从当前状态推过去）
#include<bits/stdc++.h>
using namespace std; struct Node
{
int cost,status;
int s[];
int pos;
Node(int co=,int st=,int pos=):cost(co),status(st),pos(pos){}
};
const int maxn = 4e5;
int fac[] = {,,,,,,,,};
int ways[][] = {,,-,,,,,-};
char WAYS[] = {'d','u','r','l'};
char FWAYS[]= {'u','d','l','r'};
char path[maxn],path2[maxn];
int pre[maxn],pre2[maxn];
bool vis[][maxn];
int ans;
queue<Node>que[];
Node start,ending;
char word[];
int a[],b[]; int cantor(int s[])
{
int sum = ;
for(int i=; i<=; i++)
{
int num = ;
for(int j=i+; j<=; j++)
{
if(s[j] < s[i])
num++;
}
sum += num*fac[-i];
}
return sum+;
} int Merge(int *a,int l,int r)
{
int mid = (r+l)>>;
int i=l,j=mid+;
int cnt = ;
int k = ;
while(i <= mid && j <= r)
{
if(a[i] <= a[j])
{
b[cnt++] = a[i++];
}
else
{
b[cnt++] = a[j++];
k += mid - i + ;
}
}
while(i <= mid)
b[cnt++] = a[i++];
while(j <= r)
b[cnt++] = a[j++];
for(int i=; i<cnt; i++)
{
a[l++] = b[i];
}
return k;
} void MER(int *a,int l,int r,int &cnt)
{
if(l >= r)
return;
int mid = (l+r)>>;
MER(a,l,mid,cnt);
MER(a,mid+,r,cnt);
cnt += Merge(a,l,r);
} int init(char word[])
{
memset(vis,,sizeof(vis));
for(int i=; i<=; i++)
scanf(" %c",&word[i]);
int cnt = ;
for(int i=; i<=; i++)
if((word[i]) != 'x')
a[++cnt] = word[i]-'';
int num = ;
MER(a,,cnt,num);
for(int i=; i<=; i++)
{
ending.s[i] = i;
if(word[i] == 'x')
start.s[i] = ,start.pos = i;
else
start.s[i] = word[i] - '';
}
start.status = cantor(start.s);
ending.status = cantor(ending.s);
ending.pos = ;
return (num & ) == ;
} bool bfs(int w)
{
int num = que[w].size();
while(num--)
{ Node tmp = que[w].front();
que[w].pop();
int status = tmp.status;
int cost = tmp.cost;
if(vis[w^][status])
{
ans = status;
return ;
}
int x = (tmp.pos-)/+;
int y = (tmp.pos-)%+;
for(int i=; i<; i++)
{
int xx = x+ways[i][];
int yy = y+ways[i][];
if(xx < || xx > || yy < || yy > )
continue;
Node t = tmp;
t.s[(x-)*+y] = tmp.s[(xx-)*+yy];
t.s[(xx-)*+yy] = ;
t.status = cantor(t.s);
if(vis[w][t.status])continue;
vis[w][t.status] = ;
t.s[(x-)*+y] = tmp.s[(xx-)*+yy];
t.s[(xx-)*+yy] = ;
t.cost = cost+;
t.pos = (xx-)*+yy;
if(w == )path[t.status] = WAYS[i],pre[t.status] = status;
else path2[t.status] = FWAYS[i],pre2[t.status] = status;
que[w].push(t);
}
}
return ;
} void out(int w)
{
if(pre[w] == -)
return;
out(pre[w]);
printf("%c",path[w]);
}
void out2(int w)
{
while(pre2[w] != -)
{
printf("%c",path2[w]);
w = pre2[w];
}
}
void solve()
{
while(!que[].empty())que[].pop();
while(!que[].empty())que[].pop();
que[].push(start);
que[].push(ending);
pre[start.status] = pre2[ending.status] = -;
vis[][start.status] = vis[][ending.status] = ;
while(!que[].empty() || !que[].empty())
{
if(bfs())
{
out(ans);
out2(ans);
puts("");
return;
}
if(bfs())
{
out(ans);
out2(ans);
puts("");
return;
}
}
} int main()
{
while(~scanf(" %c",&word[]))
{
if(init(word))
printf("unsolvable\n");
else
{
solve();
}
}
}