题目链接：
UVALIve 6665 Dragonas Cruller
题意：
以九宫格的形式给出0–8八个数字，然后通过移动0数字，使这个九宫格变成给定的状态，上下移动和左右移动的权值不一样，求最小移动路径值。
分析：
用康拓排序来去重。
因为上下移动和左右移动的权值不一样，所以必须使用优先队列，这样才能保证解的优先性。
然而3000MS的限制还是跑了2979MS，好险。。。。。。o(╯□╰)o
CODE：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <climits>
#include <queue>
#include <set>
#include <string>
using namespace std;const int maxn=400000;int ch,cv,ans,st,ed,pos,npos;
int ast[15],aed[15],temp[15],fac[15]={
1,1};
int vis[maxn];struct Node{int cost,pos,cantor;//当前状态下的路径值，0位置和康拓值bool operator < (const Node& a) const{return cost>a.cost;}
}cur,nextnode;void CalcFac()
{for(int i=2;i<10;i++){fac[i]=fac[i-1]*i;//计算阶乘//printf("fac[%d]=%d\n",i,fac[i]);}
}int AToInt(int a[])//数组状态装换成相应康拓值
{int x=0;for(int i=0;i<9;i++){int y=a[i];for(int j=0;j<i;j++){
//去掉已经用过的比a[i]小的值if(a[j]<a[i]) y--;}x+=fac[8-i]*y;//从右往左看是第8-i位}return x;
}void IntToA(int x,int *a)//康拓值转换成数组
{int vvis[10];memset(vvis,0,sizeof(vvis));for(int i=0;i<9;i++){int y=x/fac[8-i];//第8-i位应该是第y小的数字for(int j=0;j<9;j++){if(!vvis[j]){
//没被用过的数字if(y==0){
//这时j就是没被用过的第y大的数字vvis[j]=1,a[i]=j;break;}y--;}}x%=fac[8-i];}
}void change(int i,int flag)
{
//需要在每次i之后将temp数组还原，如果是每次i都重新调用IntToA来计算temp会TLEif(flag==1){if(i==0){npos=(pos+3)%9;//向下移动swap(temp[pos],temp[npos]);}else if(i==1){npos=(pos+6)%9;//向上移动swap(temp[pos],temp[npos]);}else if(i==2){npos=(pos+8)%9;//向左移动swap(temp[pos],temp[npos]);}else if(i==3){
//向右移动npos=(pos+1)%9;swap(temp[pos],temp[npos]);}}else swap(temp[pos],temp[npos]);//还原temp
}int bfs()
{int x;priority_queue<Node> que;memset(vis,0,sizeof(vis));cur.cost=0;cur.cantor=st;que.push(cur);vis[st]=1;int flag=0;while(!que.empty()){cur=que.top();que.pop();//printf("cur.cantor=%d cur.cost=%d\n",cur.cantor,cur.cost);if(cur.cantor==ed){x=cur.cost,flag=1;break;}//if(vis[cur.cantor]) continue;pos=cur.pos,npos;IntToA(cur.cantor,temp);for(int i=0;i<4;i++){change(i,1);nextnode.cost=cur.cost+((i<2)?cv:ch);/*printf("i=%d pos=%d npos=%d cost=%d\n",i,pos,npos,nextnode.cost);for(int j=0;j<9;j++)printf("%d",temp[j]);printf("\n");*/nextnode.pos=npos;nextnode.cantor=AToInt(temp);/*if(nextnode.cantor==ed) {x=nextnode.cost,flag=1;break;}*/if(!vis[nextnode.cantor]||vis[nextnode.cantor]>nextnode.cost){vis[nextnode.cantor]=nextnode.cost;que.push(nextnode);}change(i,0);}//if(flag) break;}return x;
}int main()
{
#ifdef LOCALfreopen("in.txt","r",stdin);
#endifCalcFac();while(~scanf("%d%d",&ch,&cv)){if(ch==0&&cv==0) break;for(int i=0;i<9;i++){scanf("%d",&ast[i]);if(ast[i]==0) cur.pos=i;}for(int i=0;i<9;i++)scanf("%d",&aed[i]);st=AToInt(ast);ed=AToInt(aed);//printf("st=%d ed=%d\n",st,ed);ans=bfs();printf("%d\n",ans);}return 0;
}
给函数加inline，稍微快了点，2692MS。。。。。。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <climits>
#include <queue>
#include <set>
#include <string>
using namespace std;const int maxn=400000;int ch,cv,ans,st,ed,pos,npos;
int ast[15],aed[15],temp[15],fac[15]={
1,1};
int vis[maxn];struct Node{int cost,pos,cantor;bool operator < (const Node& a) const{return cost>a.cost;}
}cur,nextnode;inline void CalcFac()
{for(int i=2;i<10;i++){fac[i]=fac[i-1]*i;//printf("fac[%d]=%d\n",i,fac[i]);}
}inline int ArrayToInt(int a[])
{int x=0;for(int i=0;i<9;i++){int y=a[i];for(int j=0;j<i;j++){if(a[j]<a[i]) y--;}x+=fac[8-i]*y;}return x;
}inline void IntToArray(int x,int *a)
{int vvis[10];memset(vvis,0,sizeof(vvis));for(int i=0;i<9;i++){int y=x/fac[8-i];for(int j=0;j<9;j++){if(!vvis[j]){if(y==0){vvis[j]=1,a[i]=j;break;}y--;}}x%=fac[8-i];}
}inline int bfs()
{int x;priority_queue<Node> que;memset(vis,0,sizeof(vis));cur.cost=0;cur.cantor=st;que.push(cur);vis[st]=1;int flag=0;while(!que.empty()){cur=que.top();que.pop();if(cur.cantor==ed){x=cur.cost;break;}pos=cur.pos,npos;IntToArray(cur.cantor,temp);for(int i=0;i<4;i++){if(i==0){npos=(pos+3)%9;swap(temp[pos],temp[npos]);}else if(i==1){npos=(pos+6)%9;swap(temp[pos],temp[npos]);}else if(i==2){npos=(pos+8)%9;swap(temp[pos],temp[npos]);}else if(i==3){npos=(pos+1)%9;swap(temp[pos],temp[npos]);}nextnode.cost=cur.cost+((i<2)?cv:ch);nextnode.pos=npos;nextnode.cantor=ArrayToInt(temp);if(!vis[nextnode.cantor]||vis[nextnode.cantor]>nextnode.cost){vis[nextnode.cantor]=nextnode.cost;que.push(nextnode);}swap(temp[pos],temp[npos]);}}return x;
}int main()
{
#ifdef LOCALfreopen("in.txt","r",stdin);
#endifCalcFac();while(~scanf("%d%d",&ch,&cv)){if(ch==0&&cv==0) break;for(int i=0;i<9;i++){scanf("%d",&ast[i]);if(ast[i]==0) cur.pos=i;}for(int i=0;i<9;i++)scanf("%d",&aed[i]);st=ArrayToInt(ast);ed=ArrayToInt(aed);ans=bfs();printf("%d\n",ans);}return 0;
}