先丢代码(注释即思路)
#include<bits/stdc++.h>
using namespace std;
//下面这个注释是我做题的时候对于这两种移动的草稿(用来看下标
/*
0|1|2|3|4|5|6|7|8 //位_下标 -┒
375 237 ┇
-|-|-|-|-|-|-|-|- ↓ 261 → 465 ┠→(que1)
3|7|5|2|6|1|4|8|0 ↓ 原 480 801 ┇
2|3|7|4|6|5|8|0|1 ↓ 改 -┙
-----------------------------------------------------------------------
0|1|2|3|4|5|6|7|8 //位_下标 -┒
375 375 ┇
-|-|-|-|-|-|-|-|- ↓ 261 → 126 ┠→(que2)
2|6|1 ↓ 原 480 480 ┇
1|2|6 ↓ 改 -┙
*/
struct doge{int dis;string st;doge(){dis=0,st="";}}k,tot;//dis为当前走了几步,st不是表示当前情况,而是加上了之前走过的,构造函数来初始化
char d[20]={'0','1','2','3','4','5','6','7','8'};//方便处理int转string/char
string CyaNgw="012354678",x,y;//x和y在后面间接处理情况 ,CyaNgw为终点情况
queue <doge> q;//BFS
map <string,bool> vis;//去重
string que1(string ss,string p){//根据上面的演示而来的转换公式(第一种修改)
p=ss[3]+ss[0]+ss[1]+ss[6]+ss[4]+ss[2]+ss[7]+ss[8]+ss[5];
return p;
}
string que2(string ss,string p){//根据上面的演示而来的转换公式(第二种修改)
p=ss[0]+ss[1]+ss[2]+ss[5]+ss[3]+ss[4]+ss[6]+ss[7]+ss[8];
return p;
}
int main(){
for(int i=1,a;i<=9;i++){//输入初始结果
cin>>a;
k.st+=d[a];//记录成string
}
q.push(k);//入队
while(!q.empty()){
k=q.front();q.pop();//取出队首,pop掉队首
x=que1(k.st,"");//第一种情况
y=que2(k.st,"");//第二种情况
if(x==CyaNgw||y==CyaNgw) {//如果达到终点
k.st+=CyaNgw;//加上 目标情况(也要输出
cout<<k.dis<<endl;//输出走了几步
for(int i=0;i<k.st.length();i++){
if(i%9==0)cout<<endl<<endl;//如果能被9整除,输出两个endl(刚好与第一个下标是0抵消了,刚好是9,而不是%9==1)
cout<<k.st[i]<<" ";//输出数字,空格
}
return 0;//输出完return 0
}
if(vis[x]==false){//判重 (对于que1
vis[x]=true;
k.dis++;k.st+=x;//是+=而不是=
q.push(k);//记录 ,入队
}
if(vis[y]==false){//判重 (对于que2
vis[y]=true;
k.dis++;k.st+=y;//是+=而不是=
q.push(k);//入队,记录
}
}
cout<<"UNSOLVABLE";//如果上面没有输出(有输出就会有return 0),且队列空空,那么就无解
}
思路的来源都是之前做的两道搜索:
如果你们分数上了60,你们都可以看到我的这两个题的AC记录这两个题我都是非正解
我这个题样例输出的居然是UNSOLVABLE,求助啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊