ORZ机房大佬
by 洛天依_ @ 2019-03-30 15:59:23
呵呵，初一萌新表示看不懂大佬在作甚
by XJack @ 2019-03-30 16:04:36
呀,快来帮帮我！
by ⚡GG⚡ @ 2019-03-30 16:12:47
搜索+队列优化：
```cpp
#include<bits/stdc++.h>
using namespace std;
long long ys,zz=123804765,tmp;
int a[4][4],sx,sy;
int dx[4]={-1,0,0,1};
int dy[4]={0,-1,1,0};
map<long long,int>m;
void bfs(long long ys){
queue<long long>q;
q.push(ys);
m[ys]=0;
while(!q.empty()){
long long s=q.front();
long long stmp=s;
q.pop();
if(s==zz)
return;
for(int i=3;i>=1;i--){
for(int j=3;j>=1;j--){
a[i][j]=stmp%10;
stmp/=10;
if(a[i][j]==0)
sx=i,sy=j;
}
}
for(int i=0;i<4;i++){
long long tmp=0;
int nx=sx+dx[i];
int ny=sy+dy[i];
if(nx>=1&&nx<=3&&ny>=1&&ny<=3){
swap(a[sx][sy],a[nx][ny]);
for(int i=1;i<=3;i++)
for(int j=1;j<=3;j++)
tmp=tmp*10+a[i][j];
if(m.count(tmp)==0)
{
m[tmp]=m[s]+1;
q.push(tmp);
}
swap(a[sx][sy],a[nx][ny]);
}
}
}
}
int main(){
cin>>ys;
if(ys==zz){
cout<<0<<endl;
return 0;
}
bfs(ys);
cout<<m[zz]<<endl;
return 0;
}
```
by Eason_AC @ 2019-03-30 16:23:31
@[Eason_AC](/space/show?uid=112917) 好歹解释以下呀……
by ⚡GG⚡ @ 2019-03-30 16:25:00
@[垃圾一个](/space/show?uid=85933)
cantor展开式+双向BFS
基本上是板子
应该很容易懂
```cpp
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
const int MAXN = 400000;
int step[2][MAXN],fac[10] = {1,1,2,6,24,120,720,5040,40320,362880};
bool vis[2][MAXN];
int dir[4] = {1,-3,-1,3};
inline int cantor(int a[])
{
int i,j,ans = 0;
for(i = 0;i < 9;i++)
{
int s = 0;
for(j = i + 1;j < 9;j++)
if(a[j] < a[i]) s++;
ans += s * fac[8 - i];
}
return ans;
}
struct Node
{
int word[9],loc,ca;
bool f;
void node(int Word[],int LOC,int CA,bool F)
{
for(int i = 0;i < 9;i++) word[i] = Word[i];
loc = LOC,ca = CA,f = F;
}
}Start,order;
inline int dbfs()
{
queue<Node> q;
Start.f = 1,order.f = 0;
q.push(Start);
q.push(order);
int i;
while(!q.empty())
{
Node tmp = q.front();
q.pop();
if(vis[!tmp.f][tmp.ca])
return (step[1][tmp.ca] + step[0][tmp.ca]);
int Step = step[tmp.f][tmp.ca];
for(i = 0;i < 4;i++)
{
int poss = tmp.loc + dir[i];
if(0 <= poss&&poss < 9&&(tmp.loc % 3 == poss % 3||tmp.loc / 3 == poss / 3))
{
swap(tmp.word[tmp.loc],tmp.word[poss]);
int nca = cantor(tmp.word);
if(!vis[tmp.f][nca])
{
Node g;
vis[tmp.f][nca] = 1;
step[tmp.f][nca] = Step + 1;
g.node(tmp.word,poss,nca,tmp.f);
q.push(g);
}
swap(tmp.word[tmp.loc],tmp.word[poss]);
}
}
}
return -1;
}
inline int cutdown(int a[])
{
int i,j,q = 0;
for(i = 0;i < 9;i++)
for(j = i + 1;j < 9;j++)
if(a[i] != 0&&a[j] != 0&&a[j] < a[i]) q++;
return q;
}
int useless[10] = {1,2,3,8,0,4,7,6,5};
int main()
{
int i;
for(i = 0;i < 9;i++)
{
scanf("%1d",&Start.word[i]);
if(!Start.word[i]) Start.loc = i;
}
for(i = 0;i < 9;i++)
{
order.word[i] = useless[i];
if(!order.word[i]) order.loc = i;
}
if(cutdown(Start.word) % 2 != cutdown(order.word) % 2)
{
printf("-1");
return 0;
}
Start.ca = cantor(Start.word);
vis[1][Start.ca] = 1;
order.ca = cantor(order.word);
vis[0][order.ca] = 1;
printf("%d",dbfs());
return 0;
}
```
by resftlmuttmotw @ 2019-05-12 10:55:13
来自一个蒟蒻的懵圈表情
by clarkwang @ 2019-05-26 17:24:22