AcWing 1107. 魔板(改康托展开)
原题链接
简单
作者:
ZhanSir
,
2021-05-10 10:19:53
,
所有人可见
,
阅读 241
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 6e4;
typedef pair<char,string> PCS;
int g[2][4];
int jc[20],dis[N];
bool st[N];
int dist[N];
PCS pre[N];
queue<string> q;
int kt(string state){
int res=0,len=state.size();
for(int i=0;i<len;i++){
int cnt=0;
for(int j=i+1;j<len;j++)if(state[j]<state[i])cnt++;
res+=cnt*jc[len-i-1];
}
return res;
}
void sett(string state){
for(int i=0;i<4;i++)g[0][i]=state[i];
for(int i=3,j=4;i>=0;i--,j++)g[1][i]=state[j];
}
string get(){
string res;
for(int i=0;i<4;i++)res+=g[0][i];
for(int i=3;i>=0;i--)res+=g[1][i];
return res;
}
string move0(string state){
sett(state);
for(int i=0;i<4;i++)swap(g[0][i],g[1][i]);
return get();
}
string move1(string state){
sett(state);
char v0=g[0][3],v1=g[1][3];
for(int i=3;i>0;i--)
for(int j=0;j<2;j++)
g[j][i]=g[j][i-1];
g[0][0]=v0,g[1][0]=v1;
return get();
}
string move2(string state){
sett(state);
char v=g[0][1];
g[0][1]=g[1][1];
g[1][1]=g[1][2];
g[1][2]=g[0][2];
g[0][2]=v;
return get();
}
void bfs(string start,string end){
if(start==end)return;
q.push(start);
dist[kt(start)]=0;
while(q.size()){
string t = q.front();
q.pop();
string m[3];
m[0]=move0(t);
m[1]=move1(t);
m[2]=move2(t);
for(int i=0;i<3;i++){
string str=m[i];
if(dist[kt(str)]==0){
dist[kt(str)]=dist[kt(t)]+1;
pre[kt(str)]={char(i+'A'),t};
if(str==end)break;
q.push(str);
}
}
}
}
int main(){
int x;
jc[0]=1;
for(int i=1;i<=8;i++)
jc[i]=jc[i-1]*i;
string start,end;
for(int i=0;i<8;i++){
cin>>x;
end+=char(x+'0');
}
for(int i=0;i<8;i++)start+=char(i+'1');
bfs(start,end);
cout<<dist[kt(end)]<<endl;
string res;
while(end!=start)
{
res+=pre[kt(end)].first;
end=pre[kt(end)].second;
}
reverse(res.begin(),res.end());
if(res.size())cout<<res<<endl;
return 0;
}