$$\color{Purple}{kuangbin题解目录}$$
hdu中为多数据读入,前5种境界会在hdu上tle掉,第6种境界已修改成hdu版ac(前五种可参考第6种的输入处理)
描述
在一个 $3×3$ 的网格中,$1 \\sim 8$ 这 $8$ 个数字和一个 X
恰好不重不漏地分布在这 $3×3$ 的网格中。
例如:
1 2 3
X 4 6
7 5 8
在游戏过程中,可以把 X
与其上、下、左、右四个方向之一的数字交换(如果存在)。
我们的目的是通过交换,使得网格变为如下排列(称为正确排列):
1 2 3
4 5 6
7 8 X
例如,示例中图形就可以通过让 X
先后与右、下、右三个方向的数字交换成功得到正确排列。
交换过程如下:
1 2 3 1 2 3 1 2 3 1 2 3
X 4 6 4 X 6 4 5 6 4 5 6
7 5 8 7 5 8 7 X 8 7 8 X
把 X
与上下左右方向数字交换的行动记录为 u
、d
、l
、r
。
现在,给你一个初始网格,请你通过最少的移动次数,得到正确排列。
输入格式
输入占一行,将 $3×3$ 的初始网格描绘出来。
例如,如果初始网格如下所示:
1 2 3
x 4 6
7 5 8
则输入为:1 2 3 x 4 6 7 5 8
输出格式
输出占一行,包含一个字符串,表示得到正确排列的完整行动记录。
如果答案不唯一,输出任意一种合法方案即可。
如果不存在解决方案,则输出 unsolvable
。
输入样例:
2 3 4 1 5 x 7 6 8
输出样例
ullddrurdllurdruldr
此题给出多种思路及优化,来源于csdn八数码的八大境界 ,根据它的思路重写并完善一下
思路一:反向bfs+存状态
注:此处采用$unordered\_map$不会超时,采用$map$会$tle$.
代码
//#pragma GCC optimize(2)
//暴力反向bfs+存状态
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <unordered_map>
using namespace std;
string g;
vector<int> res;
unordered_map<string,int> mp;
struct node{
string str;//状态
vector<int> v;//存过程
int pos;//x所在位置
};
int bfs(string s)//反向bfs
{
queue<node> q;
node start_;
start_.str="12345678x",start_.pos=8;//下标从0开始,也方便后面取模运算
q.push(start_);
mp[start_.str]=1;
while(q.size()>0)
{
node temp1=q.front(),temp2;
//cout << temp1.str << endl;
q.pop();
if(temp1.str==s)//能回溯到起点
{
res=temp1.v;
return 1;
}
temp2=temp1;
if((temp2.pos+1)%3!=0)//不在最右边,可右移,反向即左移
{
swap(temp2.str[temp2.pos],temp2.str[temp2.pos+1]);
temp2.pos++;
temp2.v.push_back(4);
if(mp[temp2.str]==0)
{
mp[temp2.str]=1;
q.push(temp2);
}
}
temp2=temp1;
if(temp2.pos%3!=0)//不在最左边,可左移,反向即右移
{
swap(temp2.str[temp2.pos],temp2.str[temp2.pos-1]);
temp2.pos--;
temp2.v.push_back(3);
if(mp[temp2.str]==0)
{
mp[temp2.str]=1;
q.push(temp2);
}
}
temp2=temp1;
if(temp2.pos<=5)//不在最后一行,可下移,反向即上移
{
swap(temp2.str[temp2.pos],temp2.str[temp2.pos+3]);
temp2.pos+=3;
temp2.v.push_back(2);
if(mp[temp2.str]==0)
{
mp[temp2.str]=1;
q.push(temp2);
}
}
temp2=temp1;
if(temp2.pos>=3)//不在最上面一行,可上移,反向即下移
{
swap(temp2.str[temp2.pos],temp2.str[temp2.pos-3]);
temp2.pos-=3;
temp2.v.push_back(1);
if(mp[temp2.str]==0)
{
mp[temp2.str]=1;
q.push(temp2);
}
}
}
return -1;
}
int main()
{
for(int i=1;i<=9;i++)
{
char temp_c;
scanf("%c ",&temp_c);
g+=temp_c;
}
//cout << g << endl;
int ans=bfs(g);
//cout << ans << endl;
if(ans!=-1)
{
for(int i=res.size()-1;i>=0;i--)
{//1下2上3右4左
if(res[i]==1)
printf("d");
else if(res[i]==2)
printf("u");
else if(res[i]==3)
printf("r");
else if(res[i]==4)
printf("l");
}
}
else printf("unsolvable");
return 0;
}
思路二:反向bfs+康托展开判重
康托展开核心代码
int fac[10]={1,1,2,6,24,120,720,5040,40320,362880};
int cantor(int n,int a[])//n表示个数,a[]表示该排列顺序
{
int res=0;
for(int i=0;i<=n-1;i++)
{
int cnt=0;
//内循环作用:找到a[i]是当前数列中未出现的数中的第几小
for(int j=i+1;j<=n-1;j++)
if(a[j]<a[i])
cnt++;
res+=cnt*(fac[n-1-i]);
}
return res+1;
//如果输出的是排名就要+1,普通的话就直接返回res即可
}
代码
//#pragma GCC optimize(2)
//暴力反向bfs+康托展开去重
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
string g;
vector<int> res;
struct node{
string str;//状态
vector<int> v;//存过程
int pos;//x所在位置
};
int vis[400010];
int fac[10]={1,1,2,6,24,120,720,5040,40320,362880};//阶乘
int cantor(string s)
{
int sum=0;
int temp[10];
for(int i=0;i<=8;i++)
{
if(s[i]=='x')
temp[i]=0;
else temp[i]=s[i]-'0';
}
for(int i=0;i<=8;i++)
{
int t=0;
for(int j=i+1;j<=8;j++)
if(s[j]<s[i])
t++;
sum+=t*fac[8-i];
}
return sum+1;
}
int bfs(string s)//反向bfs
{
queue<node> q;
node start_;
start_.str="12345678x",start_.pos=8;//下标从0开始,也方便后面取模运算
int end_cantor=cantor(s);
q.push(start_);
int start_cantor=cantor(start_.str);
vis[start_cantor]=1;
while(q.size()>0)
{
node temp1=q.front(),temp2;
//cout << temp1.str << endl;
q.pop();
if(cantor(temp1.str)==end_cantor)//能回溯到起点
{
res=temp1.v;
return 1;
}
temp2=temp1;
if((temp2.pos+1)%3!=0)//不在最右边,可右移,反向即左移
{
swap(temp2.str[temp2.pos],temp2.str[temp2.pos+1]);
temp2.pos++;
temp2.v.push_back(4);
int t=cantor(temp2.str);
if(vis[t]==0)
{
vis[t]=1;
q.push(temp2);
}
}
temp2=temp1;
if(temp2.pos%3!=0)//不在最左边,可左移,反向即右移
{
swap(temp2.str[temp2.pos],temp2.str[temp2.pos-1]);
temp2.pos--;
temp2.v.push_back(3);
int t=cantor(temp2.str);
if(vis[t]==0)
{
vis[t]=1;
q.push(temp2);
}
}
temp2=temp1;
if(temp2.pos<=5)//不在最后一行,可下移,反向即上移
{
swap(temp2.str[temp2.pos],temp2.str[temp2.pos+3]);
temp2.pos+=3;
temp2.v.push_back(2);
int t=cantor(temp2.str);
if(vis[t]==0)
{
vis[t]=1;
q.push(temp2);
}
}
temp2=temp1;
if(temp2.pos>=3)//不在最上面一行,可上移,反向即下移
{
swap(temp2.str[temp2.pos],temp2.str[temp2.pos-3]);
temp2.pos-=3;
temp2.v.push_back(1);
int t=cantor(temp2.str);
if(vis[t]==0)
{
vis[t]=1;
q.push(temp2);
}
}
}
return -1;
}
int main()
{
for(int i=1;i<=9;i++)
{
char temp_c;
scanf("%c ",&temp_c);
g+=temp_c;
}
//cout << g << endl;
int ans=bfs(g);
//cout << ans << endl;
if(ans!=-1)
{
for(int i=res.size()-1;i>=0;i--)
{//1下2上3右4左
if(res[i]==1)
printf("d");
else if(res[i]==2)
printf("u");
else if(res[i]==3)
printf("r");
else if(res[i]==4)
printf("l");
}
}
else printf("unsolvable");
return 0;
}
思路三:反向bfs+康托展开+打表存储
//#pragma GCC optimize(2)
//暴力反向bfs+康托展开去重+打表
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
string g;
vector<int> res[500010];
struct node{
string str;//状态
vector<int> v;//存过程
int pos;//x所在位置
};
int vis[400010];
int fac[10]={1,1,2,6,24,120,720,5040,40320,362880};//阶乘
int cantor(string s)
{
int sum=0;
int temp[10];
for(int i=0;i<=8;i++)
{
if(s[i]=='x')
temp[i]=0;
else temp[i]=s[i]-'0';
}
for(int i=0;i<=8;i++)
{
int t=0;
for(int j=i+1;j<=8;j++)
if(s[j]<s[i])
t++;
sum+=t*fac[8-i];
}
return sum+1;
}
int bfs(string s)//反向bfs
{
queue<node> q;
node start_;
start_.str="12345678x",start_.pos=8;//下标从0开始,也方便后面取模运算
int end_cantor=cantor(s);
q.push(start_);
int start_cantor=cantor(start_.str);
vis[start_cantor]=1;
while(q.size()>0)
{
node temp1=q.front(),temp2;
//cout << temp1.str << endl;
q.pop();
int pos=cantor(temp1.str);
res[pos]=temp1.v;
if(cantor(temp1.str)==end_cantor)//能回溯到起点
return 1;
temp2=temp1;
if((temp2.pos+1)%3!=0)//不在最右边,可右移,反向即左移
{
swap(temp2.str[temp2.pos],temp2.str[temp2.pos+1]);
temp2.pos++;
temp2.v.push_back(4);
int t=cantor(temp2.str);
if(vis[t]==0)
{
vis[t]=1;
q.push(temp2);
}
}
temp2=temp1;
if(temp2.pos%3!=0)//不在最左边,可左移,反向即右移
{
swap(temp2.str[temp2.pos],temp2.str[temp2.pos-1]);
temp2.pos--;
temp2.v.push_back(3);
int t=cantor(temp2.str);
if(vis[t]==0)
{
vis[t]=1;
q.push(temp2);
}
}
temp2=temp1;
if(temp2.pos<=5)//不在最后一行,可下移,反向即上移
{
swap(temp2.str[temp2.pos],temp2.str[temp2.pos+3]);
temp2.pos+=3;
temp2.v.push_back(2);
int t=cantor(temp2.str);
if(vis[t]==0)
{
vis[t]=1;
q.push(temp2);
}
}
temp2=temp1;
if(temp2.pos>=3)//不在最上面一行,可上移,反向即下移
{
swap(temp2.str[temp2.pos],temp2.str[temp2.pos-3]);
temp2.pos-=3;
temp2.v.push_back(1);
int t=cantor(temp2.str);
if(vis[t]==0)
{
vis[t]=1;
q.push(temp2);
}
}
}
return -1;
}
int main()
{
for(int i=1;i<=9;i++)
{
char temp_c;
scanf("%c ",&temp_c);
g+=temp_c;
}
//cout << g << endl;
int ans=bfs(g);
//cout << ans << endl;
int end_cantor=cantor(g);
if(ans!=-1)
{
for(int i=res[end_cantor].size()-1;i>=0;i--)
{//1下2上3右4左
if(res[end_cantor][i]==1)
printf("d");
else if(res[end_cantor][i]==2)
printf("u");
else if(res[end_cantor][i]==3)
printf("r");
else if(res[end_cantor][i]==4)
printf("l");
}
}
else printf("unsolvable");
return 0;
}
思路四:反向bfs+康托展开+打表存储+路径回溯——类似于链式前向星
//#pragma GCC optimize(2)
//暴力反向bfs+康托展开去重+打表
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
string g;
/***更改部分***/
struct res{
int now;
int fa;
}res[500010];
/***更改部分***/
struct node{
string str;//状态
int index;//第几个
/***增加index***/
int pos;//x所在位置
};
int vis[400010],cnt;
int fac[10]={1,1,2,6,24,120,720,5040,40320,362880};//阶乘
int cantor(string s)
{
int sum=0;
int temp[10];
for(int i=0;i<=8;i++)
{
if(s[i]=='x')
temp[i]=0;
else temp[i]=s[i]-'0';
}
for(int i=0;i<=8;i++)
{
int t=0;
for(int j=i+1;j<=8;j++)
if(s[j]<s[i])
t++;
sum+=t*fac[8-i];
}
return sum+1;
}
int bfs(string s)//反向bfs
{
queue<node> q;
node start_;
start_.str="12345678x",start_.pos=8,start_.index=0;//下标从0开始,也方便后面取模运算
int end_cantor=cantor(s);
q.push(start_);
int start_cantor=cantor(start_.str);
/***增加部分***/
vis[start_cantor]=0;
cnt=1;
/***增加部分***/
while(q.size()>0)
{
node temp1=q.front(),temp2;
//cout << temp1.str << endl;
q.pop();
if(cantor(temp1.str)==end_cantor)//能回溯到起点
return 1;
temp2=temp1;
if((temp2.pos+1)%3!=0)//不在最右边,可右移,反向即左移
{
swap(temp2.str[temp2.pos],temp2.str[temp2.pos+1]);
temp2.pos++;
/***修改部分***/
res[cnt].now=4,res[cnt].fa=temp2.index,temp2.index=cnt++;
/***修改部分***/
int t=cantor(temp2.str);
/***修改部分***/
if(vis[t]==-1)
{
vis[t]=cnt-1;
q.push(temp2);
}
/***修改部分***/
}
temp2=temp1;
if(temp2.pos%3!=0)//不在最左边,可左移,反向即右移
{
swap(temp2.str[temp2.pos],temp2.str[temp2.pos-1]);
temp2.pos--;
/***修改部分***/
res[cnt].now=3,res[cnt].fa=temp2.index,temp2.index=cnt++;
/***修改部分***/
int t=cantor(temp2.str);
/***修改部分***/
if(vis[t]==-1)
{
vis[t]=cnt-1;
q.push(temp2);
}
/***修改部分***/
}
temp2=temp1;
if(temp2.pos<=5)//不在最后一行,可下移,反向即上移
{
swap(temp2.str[temp2.pos],temp2.str[temp2.pos+3]);
temp2.pos+=3;
/***修改部分***/
res[cnt].now=2,res[cnt].fa=temp2.index,temp2.index=cnt++;
/***修改部分***/
int t=cantor(temp2.str);
/***修改部分***/
if(vis[t]==-1)
{
vis[t]=cnt-1;
q.push(temp2);
}
/***修改部分***/
}
temp2=temp1;
if(temp2.pos>=3)//不在最上面一行,可上移,反向即下移
{
swap(temp2.str[temp2.pos],temp2.str[temp2.pos-3]);
temp2.pos-=3;
/***修改部分***/
res[cnt].now=1,res[cnt].fa=temp2.index,temp2.index=cnt++;
/***修改部分***/
int t=cantor(temp2.str);
/***修改部分***/
if(vis[t]==-1)
{
vis[t]=cnt-1;
q.push(temp2);
}
/***修改部分***/
}
}
return -1;
}
int main()
{
/***增添部分***/
memset(vis,-1,sizeof(vis));
res[0].now=-1;
/***增添部分***/
for(int i=1;i<=9;i++)
{
char temp_c;
scanf("%c ",&temp_c);
g+=temp_c;
}
//cout << g << endl;
int ans=bfs(g);
//cout << ans << endl;
int end_cantor=cantor(g);
//cout << end_cantor << ' ' << vis[end_cantor] << endl;
/***修改部分***/
if(vis[end_cantor]!=-1)
{
int t=vis[end_cantor];
while(res[t].now!=-1)
{
//cout << res[t].now << "***" << endl;
if(res[t].now==1)
printf("d");
else if(res[t].now==2)
printf("u");
else if(res[t].now==3)
printf("r");
else if(res[t].now==4)
printf("l");
t=res[t].fa;
}
}/***修改部分***/
else printf("unsolvable");
return 0;
}
思路五;双向bfs+康托展开判重+回溯记录路径
//#pragma GCC optimize(2)
//双向bfs+康托展开去重
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
string g;
/***更改部分***/
struct res{
int now;
int fa;
}res1[500010],res2[500010];
/***更改部分***/
struct node{
string str;//状态
int index;//第几个
int status;//状态(1为起点,0为终点)
int pos;//x所在位置
};
int vis1[400010],vis2[400010],cnt1,cnt2,ans1,ans2,sum1,sum2;
int fac[10]={1,1,2,6,24,120,720,5040,40320,362880};//阶乘
int cantor(string s)
{
int sum=0;
int temp[10];
for(int i=0;i<=8;i++)
{
if(s[i]=='x')
temp[i]=0;
else temp[i]=s[i]-'0';
}
for(int i=0;i<=8;i++)
{
int t=0;
for(int j=i+1;j<=8;j++)
if(s[j]<s[i])
t++;
sum+=t*fac[8-i];
}
return sum+1;
}
int dbfs(string s,int x_pos)//双向bfs
{
queue<node> q;
node start_,end_;
start_.str="12345678x",start_.pos=8,start_.index=start_.status=0;//下标从0开始,也方便后面取模运算
int end_cantor=cantor(s);
q.push(start_);
int start_cantor=cantor(start_.str);
vis1[start_cantor]=0;
end_.str=s,end_.pos=x_pos,end_.status=1,end_.index=0;
vis2[end_cantor]=0;
q.push(end_);
sum1=sum2=cnt1=cnt2=1;
while(q.size()>0)
{
node temp1=q.front(),temp2;
q.pop();
if(temp1.status==0)
sum1--;
else sum2--;
int temp_cantor=cantor(temp1.str);
if(temp1.status==0&&vis2[temp_cantor]!=-1)
{
ans1=temp1.index;
ans2=vis2[temp_cantor];
return 1;
}
if(temp1.status==1&&vis1[temp_cantor]!=-1)
{
ans2=temp1.index;
ans1=vis1[temp_cantor];
return 1;
}
temp2=temp1;
if((temp2.pos+1)%3!=0)//不在最右边,可右移,反向即左移
{
swap(temp2.str[temp2.pos],temp2.str[temp2.pos+1]);
temp2.pos++;
if(temp2.status==0)
res1[cnt1].now=4,res1[cnt1].fa=temp2.index,temp2.index=cnt1,cnt1++;
else res2[cnt2].now=4,res2[cnt2].fa=temp2.index,temp2.index=cnt2,cnt2++;
int t=cantor(temp2.str);
if(vis1[t]==-1&&temp2.status==0)
{
vis1[t]=temp2.index;
q.push(temp2);
sum1++;
}
else if(vis2[t]==-1&&temp2.status==1)
{
vis2[t]=temp2.index;
q.push(temp2);
sum2++;
}
}
temp2=temp1;
if(temp2.pos%3!=0)//不在最左边,可左移,反向即右移
{
swap(temp2.str[temp2.pos],temp2.str[temp2.pos-1]);
temp2.pos--;
if(temp2.status==0)
res1[cnt1].now=3,res1[cnt1].fa=temp2.index,temp2.index=cnt1,cnt1++;
else res2[cnt2].now=3,res2[cnt2].fa=temp2.index,temp2.index=cnt2,cnt2++;
int t=cantor(temp2.str);
if(vis1[t]==-1&&temp2.status==0)
{
vis1[t]=temp2.index;
q.push(temp2);
sum1++;
}
else if(vis2[t]==-1&&temp2.status==1)
{
vis2[t]=temp2.index;
q.push(temp2);
sum2++;
}
}
temp2=temp1;
if(temp2.pos<=5)//不在最后一行,可下移,反向即上移
{
swap(temp2.str[temp2.pos],temp2.str[temp2.pos+3]);
temp2.pos+=3;
if(temp2.status==0)
res1[cnt1].now=2,res1[cnt1].fa=temp2.index,temp2.index=cnt1,cnt1++;
else res2[cnt2].now=2,res2[cnt2].fa=temp2.index,temp2.index=cnt2,cnt2++;
int t=cantor(temp2.str);
if(vis1[t]==-1&&temp2.status==0)
{
vis1[t]=temp2.index;
q.push(temp2);
sum1++;
}
else if(vis2[t]==-1&&temp2.status==1)
{
vis2[t]=temp2.index;
q.push(temp2);
sum2++;
}
}
temp2=temp1;
if(temp2.pos>=3)//不在最上面一行,可上移,反向即下移
{
swap(temp2.str[temp2.pos],temp2.str[temp2.pos-3]);
temp2.pos-=3;
if(temp2.status==0)
res1[cnt1].now=1,res1[cnt1].fa=temp2.index,temp2.index=cnt1,cnt1++;
else res2[cnt2].now=1,res2[cnt2].fa=temp2.index,temp2.index=cnt2,cnt2++;
int t=cantor(temp2.str);
if(vis1[t]==-1&&temp2.status==0)
{
vis1[t]=temp2.index;
q.push(temp2);
sum1++;
}
else if(vis2[t]==-1&&temp2.status==1)
{
vis2[t]=temp2.index;
q.push(temp2);
sum2++;
}
}
if(sum1==0||sum2==0)
return 0;
}
return 0;
}
int main()
{
memset(vis1,-1,sizeof(vis1));
memset(vis2,-1,sizeof(vis2));
ans1=ans2=res1[0].now=res2[0].now=-1;
int x_pos=0;
for(int i=1;i<=9;i++)
{
char temp_c;
scanf("%c ",&temp_c);
if(temp_c=='x')
x_pos=i-1;
g+=temp_c;
}
//cout << x_pos << endl;
if(dbfs(g,x_pos))
{
vector<int> v;
if(res2[ans2].now==-1&&res1[ans1].now==-1)
{
printf("lr\n");
exit(0);
}
while(res2[ans2].now!=-1)
v.push_back(res2[ans2].now),ans2=res2[ans2].fa;
for(int i=v.size()-1;i>=0;i--)
{
if(v[i]==1)
printf("u");
else if(v[i]==2)
printf("d");
else if(v[i]==3)
printf("l");
else if(v[i]==4)
printf("r");
}
while(res1[ans1].now!=-1)
{
if(res1[ans1].now==1)
printf("d");
else if(res1[ans1].now==2)
printf("u");
else if(res1[ans1].now==3)
printf("r");
else if(res1[ans1].now==4)
printf("l");
ans1=res1[ans1].fa;
}
}
else printf("unsolvable\n");
return 0;
}
思路六:双向bfs+康托展开判重+回溯记录路径+逆序对奇数无解
//#pragma GCC optimize(2)
//双向bfs+康托展开去重
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
string g;
/***更改部分***/
struct res{
int now;
int fa;
}res1[500010],res2[500010];
/***更改部分***/
struct node{
string str;//状态
int index;//第几个
int status;//状态(1为起点,0为终点)
int pos;//x所在位置
};
int vis1[400010],vis2[400010],cnt1,cnt2,ans1,ans2,sum1,sum2;
int fac[10]={1,1,2,6,24,120,720,5040,40320,362880};//阶乘
int cantor(string s)
{
int sum=0;
int temp[10];
for(int i=0;i<=8;i++)
{
if(s[i]=='x')
temp[i]=0;
else temp[i]=s[i]-'0';
}
for(int i=0;i<=8;i++)
{
int t=0;
for(int j=i+1;j<=8;j++)
if(s[j]<s[i])
t++;
sum+=t*fac[8-i];
}
return sum+1;
}
int dbfs(string s,int x_pos)//双向bfs
{
queue<node> q;
node start_,end_;
start_.str="12345678x",start_.pos=8,start_.index=start_.status=0;//下标从0开始,也方便后面取模运算
int end_cantor=cantor(s);
q.push(start_);
int start_cantor=cantor(start_.str);
vis1[start_cantor]=0;
end_.str=s,end_.pos=x_pos,end_.status=1,end_.index=0;
vis2[end_cantor]=0;
q.push(end_);
sum1=sum2=cnt1=cnt2=1;
while(q.size()>0)
{
node temp1=q.front(),temp2;
q.pop();
if(temp1.status==0)
sum1--;
else sum2--;
int temp_cantor=cantor(temp1.str);
if(temp1.status==0&&vis2[temp_cantor]!=-1)
{
ans1=temp1.index;
ans2=vis2[temp_cantor];
return 1;
}
if(temp1.status==1&&vis1[temp_cantor]!=-1)
{
ans2=temp1.index;
ans1=vis1[temp_cantor];
return 1;
}
temp2=temp1;
if((temp2.pos+1)%3!=0)//不在最右边,可右移,反向即左移
{
swap(temp2.str[temp2.pos],temp2.str[temp2.pos+1]);
temp2.pos++;
if(temp2.status==0)
res1[cnt1].now=4,res1[cnt1].fa=temp2.index,temp2.index=cnt1,cnt1++;
else res2[cnt2].now=4,res2[cnt2].fa=temp2.index,temp2.index=cnt2,cnt2++;
int t=cantor(temp2.str);
if(vis1[t]==-1&&temp2.status==0)
{
vis1[t]=temp2.index;
q.push(temp2);
sum1++;
}
else if(vis2[t]==-1&&temp2.status==1)
{
vis2[t]=temp2.index;
q.push(temp2);
sum2++;
}
}
temp2=temp1;
if(temp2.pos%3!=0)//不在最左边,可左移,反向即右移
{
swap(temp2.str[temp2.pos],temp2.str[temp2.pos-1]);
temp2.pos--;
if(temp2.status==0)
res1[cnt1].now=3,res1[cnt1].fa=temp2.index,temp2.index=cnt1,cnt1++;
else res2[cnt2].now=3,res2[cnt2].fa=temp2.index,temp2.index=cnt2,cnt2++;
int t=cantor(temp2.str);
if(vis1[t]==-1&&temp2.status==0)
{
vis1[t]=temp2.index;
q.push(temp2);
sum1++;
}
else if(vis2[t]==-1&&temp2.status==1)
{
vis2[t]=temp2.index;
q.push(temp2);
sum2++;
}
}
temp2=temp1;
if(temp2.pos<=5)//不在最后一行,可下移,反向即上移
{
swap(temp2.str[temp2.pos],temp2.str[temp2.pos+3]);
temp2.pos+=3;
if(temp2.status==0)
res1[cnt1].now=2,res1[cnt1].fa=temp2.index,temp2.index=cnt1,cnt1++;
else res2[cnt2].now=2,res2[cnt2].fa=temp2.index,temp2.index=cnt2,cnt2++;
int t=cantor(temp2.str);
if(vis1[t]==-1&&temp2.status==0)
{
vis1[t]=temp2.index;
q.push(temp2);
sum1++;
}
else if(vis2[t]==-1&&temp2.status==1)
{
vis2[t]=temp2.index;
q.push(temp2);
sum2++;
}
}
temp2=temp1;
if(temp2.pos>=3)//不在最上面一行,可上移,反向即下移
{
swap(temp2.str[temp2.pos],temp2.str[temp2.pos-3]);
temp2.pos-=3;
if(temp2.status==0)
res1[cnt1].now=1,res1[cnt1].fa=temp2.index,temp2.index=cnt1,cnt1++;
else res2[cnt2].now=1,res2[cnt2].fa=temp2.index,temp2.index=cnt2,cnt2++;
int t=cantor(temp2.str);
if(vis1[t]==-1&&temp2.status==0)
{
vis1[t]=temp2.index;
q.push(temp2);
sum1++;
}
else if(vis2[t]==-1&&temp2.status==1)
{
vis2[t]=temp2.index;
q.push(temp2);
sum2++;
}
}
if(sum1==0||sum2==0)
return 0;
}
return 0;
}
int main()
{
string s;
while(cin >> s)
{
memset(vis1,-1,sizeof(vis1));
memset(vis2,-1,sizeof(vis2));
ans1=ans2=res1[0].now=res2[0].now=-1;
int x_pos=0;
g="";
if(s[0]=='x')
x_pos=0;
g+=s[0];
for(int i=2;i<=9;i++)
{
cin >> s;
if(s[0]=='x')
x_pos=i-1;
g+=s[0];
}
int num=0;
for(int i=0;i<=8;i++)
for(int j=0;j<i;j++)
{
int x,y;
if(g[i]=='x')
continue;
else x=g[i]-'0';
if(g[j]=='x')
continue;
else y=g[j]-'0';
if(y>x)//逆序对
num++;
}
if(num%2==1)
{
printf("unsolvable\n");
continue;
}
//cout << x_pos << endl;
if(dbfs(g,x_pos))
{
vector<int> v;
if(res2[ans2].now==-1&&res1[ans1].now==-1)
{
printf("lr\n");
continue;
}
while(res2[ans2].now!=-1)
v.push_back(res2[ans2].now),ans2=res2[ans2].fa;
for(int i=v.size()-1;i>=0;i--)
{
if(v[i]==1)
printf("u");
else if(v[i]==2)
printf("d");
else if(v[i]==3)
printf("l");
else if(v[i]==4)
printf("r");
}
while(res1[ans1].now!=-1)
{
if(res1[ans1].now==1)
printf("d");
else if(res1[ans1].now==2)
printf("u");
else if(res1[ans1].now==3)
printf("r");
else if(res1[ans1].now==4)
printf("l");
ans1=res1[ans1].fa;
}
printf("\n");
}
else printf("unsolvable\n");
}
return 0;
}
思路七:A*算法+逆序对判无解
// Problem: 八数码
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/description/181/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Date: 2023-02-07 13:53:41
//
// Powered by CP Editor (https://cpeditor.org)
/**
* @author : SDTBU_LY
* @version : V1.0.0
* @上联 : ac自动机fail树上dfs序建可持久化线段树
* @下联 : 后缀自动机的next指针DAG图上求SG函数
**/
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<unordered_map>
using namespace std;
typedef long long ll;
typedef pair<int,string> PIS;
int f(string s)//估价函数
{
int res=0;
for(int i=0;i<=8;i++)
if(s[i]!='x')
{
int num=s[i]-'1';
res+=abs(i/3-num/3)+abs(i%3-num%3);
}
return res;
}
char op[]="udlr";
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
string bfs(string start_)
{
string end_="12345678x";
unordered_map<string,int> dist;
priority_queue<PIS,vector<PIS>,greater<PIS> > q;
unordered_map<string,pair<string,char> > last;
q.push({f(start_),start_});
dist[start_]=0;
while(q.size()>0)
{
PIS temp=q.top();
q.pop();
string temp_s=temp.second;
if(temp_s==end_)
break;
int x=0,y=0;
for(int i=0;i<=8;i++)
if(temp_s[i]=='x')
{
x=i/3,y=i%3;
break;
}
string tempp=temp_s;
for(int i=0;i<=3;i++)
{
int dx=x+dir[i][0],dy=y+dir[i][1];
if(dx<0||dx>=3||dy<0||dy>=3)
continue;
swap(temp_s[dx*3+dy],temp_s[x*3+y]);
if(dist.count(temp_s)==0||dist[temp_s]>dist[tempp]+1)
{
dist[temp_s]=dist[tempp]+1;
q.push({f(temp_s)+dist[temp_s],temp_s});
last[temp_s]={tempp,op[i]};
}
temp_s=tempp;
}
}
string res;
while(end_!=start_)
{
res+=last[end_].second;
end_=last[end_].first;
}
reverse(res.begin(),res.end());
return res;
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0),cout.tie(0);
string s;
string start_;
while(cin >> s)
{
start_="";
start_+=s[0];
for(int i=2;i<=9;i++)
{
cin >> s;
start_+=s[0];
}
int num=0;
for(int i=0;i<=8;i++)
for(int j=0;j<i;j++)
{
int x,y;
if(start_[i]=='x')
continue;
else x=start_[i]-'0';
if(start_[j]=='x')
continue;
else y=start_[j]-'0';
if(y>x)//逆序对
num++;
}
if(num%2==1)
printf("unsolvable\n");
else cout << bfs(start_) << endl;
}
return 0;
}