撰写描述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:
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.
输入You will receive a deｓｃｒｉｐｔion of a configuration of the 8 puzzle. The deｓｃｒｉｐｔion 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
输出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.样例输入
2 3 4 1 5 x 7 6 8
样例输出
ullddrurdllurdruldr
题解：这题我写了一份代码，输出的步数相同但是答案不同，不知道是哪里的问题，也不知道是不是评测数据只有一种顺序。
-
- f(state)=当前状态所有数字与目标的曼哈顿距离之和。
- 初态与终态逆序队奇偶性相同则可达。
- 我用的map当作hash，但用康托展开更优。
- 存下别人的AC代码：
-
#include<bits/stdc++.h>//懒得再debug了...随便找个代码交了 using namespace std; int a[10],f[4][4],vis[1000010],pre[1000010],path[1000010]; const int dr[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; char op[4]={'u','d','l','r'}; char c[10]; struct node{ int st,d,g,pos; int s[10]; }; struct comp{ int operator( )(node u,node v) { return u.d>v.d; } }; priority_queue<node,vector<node>,comp > q; int cantor(int *p){//康托展开 int k=0,ans=0; for(register int i=1;i<=9;++i){ int sum=0,c=1; for(register int j=i+1;j<=9;++j){ if(p[j]<p[i])sum++; c*=(9-j+1); } ans+=c*sum; } return ans; } void output(int x){ if(pre[x]==-1)return; output(pre[x]); putchar(path[x]); } int value(int *x){ int sum=0; for(register int i=1;i<=9;++i)if(x[i]!=9){ int u=(i-1)/3+1,v=(i-1)%3+1; int u1=(x[i]-1)/3+1,v1=(x[i]-1)%3+1; sum+=abs(u1-u)+abs(v1-v); } return sum; } int main( ){ int x,y,z,k=0,k1=0; node now; for(int i=1;i<=3;++i) for(int j=1;j<=3;++j){ scanf("%s",c); if(c[0]!='x'){ a[++k]=c[0]-'0'; now.s[++k1]=c[0]-'0'; } else{ now.s[++k1]=9;now.pos=k1; } } int ans=0; for(int i=1;i<=8;++i) for(int j=i+1;j<=8;++j) if(a[j]<a[i])ans++; if(ans%2==1){ printf("unsolvable\n"); return 0; } k=0; now.st=cantor(now.s); int t=0; now.g=0; now.d=value(now.s); q.push(now); pre[now.st]=-1; vis[now.st]=1; int flag=0; while(q.size( )){ now=q.top( );q.pop( ); if(now.st==t){ flag=1; break; } x=(now.pos-1)/3+1;//得到位置 y=(now.pos-1)%3+1; for(int i=0;i<4;++i){ int u=x+dr[i][0],v=y+dr[i][1]; if(u>3 || u<1 || v>3 || v<1)continue; node tmp; tmp=now; tmp.s[(x-1)*3+y]=tmp.s[(u-1)*3+v]; tmp.s[(u-1)*3+v]=9; tmp.st=cantor(tmp.s); if(!vis[tmp.st]){ vis[tmp.st]=1; tmp.pos=(u-1)*3+v; tmp.g++; tmp.d=tmp.g+value(tmp.s); pre[tmp.st]=now.st; path[tmp.st]=op[i]; q.push(tmp); } } } output(0); return 0; } }
以及我的夭折代码：
//#include<bits/stdc++.h>
#include<algorithm>
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cstdio>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define P(a,b,c) make_pair(a,make_pair(b,c))
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define CLR(vis) memset(vis,0,sizeof(vis))
#define MST(vis,pos) memset(vis,pos,sizeof(vis))
#define pb push_back
//#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef pair<int,pair<int,int> >pii;
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1000000007;
const int INF = 0x3f3f3f3f;
ll gcd(ll a, ll b) {
return b ? gcd(b, a%b) : a;
}
template<class T>inline void gmax(T &A, T B) {
(A<B)&&(A=B);//if(B>A)A=B;
}
template<class T>inline void gmin(T &A, T B) {
(A>B)&&(A=B);//if(B<A)A=B;
}
template <class T>
inline bool scan_d(T &ret) {
char c;
int sgn;
if(c=getchar(),c==EOF) return 0; //EOF
while(c!='?'&&(c<'0'||c>'9')) c=getchar();
sgn=(c=='?')?-1:1;
ret=(c=='?')?0:(c-'0');
while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
ret*=sgn;
return 1;
}
inline void outt(int x) {
if(x>9) outt(x/10);
putchar(x%10+'0');
}
map<int,int>mp;
int st=0;
int ed=123456780;
int G[10]= {33,11,12,13,21,22,23,31,32,0};
map<ll,ll>pre;
const int base=1e9;
int f(int s) {
int sum=0;
per(i,1,3) {
per(j,1,3) {
int t=s%10;
s/=10;
int x=G[t]/10;
int y=G[t]%10;
sum+=abs(i-x)+abs(j-y);
}
}
return sum;
}
struct node {
int s;
int cnt;
node(int _s=0,int _cnt=0):s(_s),cnt(_cnt) {};
bool operator < (const node &a)const {
return cnt>a.cnt;
}
};
priority_queue<node>q;
int dir[4][2]= {{-1,0},{1,0},{0,-1},{0,1}};
bool ojbk(int x,int y) {
if(x<=3&&x>0&&y<=3&&y>0)return true;
return false;
}
void Swap(int &x,int &y) {
x^=y;
y^=x;
x^=y;
}
ll get_state(int t[][4]) {
int ss=0;
rep(i,1,3) {
rep(j,1,3) {
ss=ss*10+t[i][j];
}
}
}
void dfs(ll ss) {
if(pre[ss]==-1) {
return ;
}
ll state=pre[ss];
dfs(state%base);
int D=state/base;
int t[4][4];
// state%=base;
// per(i,1,3){
// per(j,1,3){
// t[i][j]=state%10;
// state/=10;
// }
// }
// rep(i,1,3){
// rep(j,1,3){
// cout<<t[i][j]<<" ";
// }
// cout<<endl;
// }
// cout<<endl;
/*
2 3 4 1 5 x 7 6 8
dlurullddrurdllurdr
*/
switch(D) {
case 0:
printf("u");
break;
case 1:
printf("d");
break;
case 2:
printf("l");
break;
case 3:
printf("r");
break;
}
}
/* 1 2 3
x 4 6
7 5 8
1 3 2
4 6 5
X 7 8
*/
void A_() {
while(!q.empty())q.pop();
q.push(node(st,0+f(st)));
node tmp;
pre[st]=-1;
while(!q.empty()) {
tmp=q.top();
q.pop();
int state=tmp.s;
int cnt=tmp.cnt;
if(state==ed) {
dfs(state);
return;
}
int t[4][4];
int ss=state;
int x,y;
per(i,1,3)
per(j,1,3) {
t[i][j]=ss%10,ss/=10;
if(t[i][j]==0)x=i,y=j;
}
rep(i,0,3) {
int xx=x+dir[i][0],yy=y+dir[i][1];
if(ojbk(xx,yy)) {
Swap(t[x][y],t[xx][yy]);
ss=get_state(t);
if(pre[(ll)ss]){
Swap(t[x][y],t[xx][yy]);
continue;
}
pre[(ll)ss]=(ll)(i*1e9+state);
if(ss==ed){
dfs(ss);return ;
}
q.push(node(ss,cnt+1-f(state)+f(ss)));
Swap(t[x][y],t[xx][yy]);
}
}
}
}
int main() {
char s[10];
int a[10];
int cnt=0;
rep(i,1,9) {
scanf("%s", s);
if(s[0]!='x') st=st*10+s[0]-'0',a[++cnt]=s[0]-'0';
else st*=10;
}
if(st==ed)cout<<"";
int ans=0;
for(int i=1;i<=8;++i)
for(int j=i+1;j<=8;++j)
if(a[j]<a[i])ans++;
if(ans%2==1)printf("unsolvable\n");
else A_();
return 0;
}