| Accepted |
3164K |
219MS |
G++ |
3644B |
经典题感觉就是不一样。
总是花了很长时间浪费在一些无关紧要的地方，把方向理解错了，正好相反的，调了N久。
后来输出的时候，都往反方向输出A了。
用康托展开做哈希函数，直接BFS就可以了
#include<iostream>
#include<cstring>
using namespace std;
int fac[10]={1,1,2,6,24,120,720,5040,40320,362880};
void swap(int &a, int &b)
{
int t=a; a=b; b=t;
}
int cantor(int x)
{
int a[10]={0};
for(int i=9; i>=1; i--)
{
a[i]=x%10;
x/=10;
}
int ans=0;
for(int i=1; i<=9; i++)
{
int c=0;
for(int j=i+1; j<=9; j++)
if(a[j]<a[i])c++;
ans+=c*fac[a[i]-1];
}
return ans;
}
struct type
{
int last;
int now;
int move;
}Q[362885];
bool used[362885]={0};
bool change(int &x, int ch)//方向理解反了，调r时其实是调l
{
int status[4][4],temp=x;
int row,column;
for(int i=3; i>=1; i--)
for(int j=3; j>=1; j--)
{
status[i][j]=temp%10;
temp/=10;
if(status[i][j]==9)
{ row=i; column=j; }
}
switch(ch)
{
case 1: if(column==1)return false; //r
swap(status[row][column], status[row][column-1]); break;
case 2: if(column==3)return false; //l
swap(status[row][column], status[row][column+1]);break;
case 3: if(row==3)return false; //u
swap(status[row][column], status[row+1][column]); break;
case 4: if(row==1) return false; //d
swap(status[row][column], status[row-1][column]); break;
}
temp=0;
for(int i=1; i<=3; i++)
for(int j=1; j<=3; j++)
temp=temp*10+status[i][j];
x=temp;
return true;
}
int main()
{
int now=0;
int goal=0;
char t;
for(int i=1; i<=9; i++)
{
cin>>t;
if(t=='x')t='9';
now=now*10+int(t-'0');
}
int l=1,r=1;
Q[1].last=0; Q[1].now=now;
int x=cantor(now);
used[x]=1;
bool find=false;
while(l<=r&&find==false&&r<=362881)
{
int num=Q[l].now, can;
int temp;
//system("pause");
for(int i=1; i<=4; i++)
{
temp=num;
if(change(temp,i))
{
can=cantor(temp);
if(!used[can])
{
used[can]=true;
r++;
Q[r].now=temp;
Q[r].last=l;
Q[r].move=i;
}
if(can==goal){find=true; break; }
}
}
l++;
}
if(find==false)cout<<"unsolvable"<<endl;
else
{
int ans[1000]; int len=0;
for( ;r!=1; )
{
len++;
ans[len]=Q[r].move;
r=Q[r].last;
}
for(int i=len; i>=1; i--)
{
switch(ans[i])
{
case 2:cout<<'r';break;//调一下输出顺序A了
case 1:cout<<'l';break;
case 4:cout<<'u';break;
case 3:cout<<'d';break;
}
}
cout<<endl;
}
system("pause");
return 0;
}