链接：https://vjudge.net/problem/POJ-1077
申明：本题没有AC，因为存在多解情况下没有明确说选择哪条路径，所以不同bfs方法出来的最优路径可能有所不同。
第一个练习的bfs问题，采取了比较简化的做法，没有优化纯粹暴力，先说下关键思路。
1、用一个九位数来表示当前33棋盘的状态
2、用一个map映射line来判重，如果没重复则将值赋为1
3、用一个map映射distance1来记录距离，每次都在上一个状态上加一的距离
4、用一个map映射gogo来记录移动的方法，用string类字符相加即可完成
5、正常bfs中queue来作为队列
6、用一个trans函数来把9位数还原为33的棋盘
没有什么太大的难点，就是优化以后厉害了再进行吧，现在水平只能写出这个样子了。。。
代码：
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<string>
using namespace std;
map<int,int> line; //记录是否出现过当前状态
queue<int> all;//bfs队列
map<int,int> distance1;//记录距离
map<int,string> gogo; //记录移动方式
int x,y;//记录当前0所在位置的坐标
int a[9];//九宫格数组
int gox[4]={0,0,1,-1};//x移动方式
int goy[4] = {1,-1,0,0};//y移动方式
char go[5] = "udrl";//移动命令
int flag = 0;//判断是否已经求出解
int judge(){//转换为9位数
return a[8] * 100000000+a[7] * 10000000+a[6] * 1000000+a[5] * 100000+a[4] * 10000+a[3] * 1000+a[2] * 100+a[1] * 10+a[0];
}
void trans(int re){//9位数翻译回3*3棋盘
if(re==0)return ;
for(int i = 0;i<=8;i++){
a[i] = re%10;
if(a[i]==0){x = i/3;y=i%3;}
re/=10;
}
}
void bfs(){//广搜
int n;//判断并记录队首元素
if(!all.empty()){
n = all.front();
all.pop();
}
else n = 0;
for(int i=0;i<4;i++){
trans(n);
int tx = x+gox[i];//移动x
int ty = y+goy[i];//移动y
if(tx>=0&&tx<3&&ty>=0&&ty<3){
//cout<<judge()<<endl;
int temp1 = judge();//储存变化前状态的9位数
int temp = a[tx3+ty];
a[tx3+ty] = 0;
a[x*3+y] = temp;
x = tx;
y = ty;
if(line[judge()]==1)continue;
else{
line[judge()] = 1;
all.push(judge());//入队
distance1[judge()] = distance1[temp1] + 1;//距离增加
gogo[judge()] = gogo[temp1] + go[i];//移动方式更新
if(judge()==result){cout<<gogo[judge()]<<endl;cout<<distance1[judge()]<<endl;flag = 1;return;}
}
}
}
bfs();
if(flag==1)return;
}
int main(){
int now;
for(int i=0;i<9;i++){cin>>a[i];if(a[i]==0){x=i/3;y=i%3;}}
for(int i=0;i<9;i++){cin>>now;result+=now*pow(10,i);}
distance1[judge()] = 0;//初始化距离
gogo[judge()] = "";//初始化移动方式位空
cout<<judge()<<endl;
cout<<result<<endl;
bfs();
return 0;
}
好吧上述版本有点问题，例如测试数据：
2 6 4 1 3 7 0 5 8
8 1 5 7 3 6 4 0 2
这个要移动31次，原程序递归好像栈溢出了。。。。。。。
解决方法：把bfs中的递归改成while循环判断即可。。
代码：
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<string>
using namespace std;
map<int,int> line; //记录是否出现过当前状态
queue<int> all;//bfs队列
map<int,int> distance1;//记录距离
map<int,string> gogo; //记录移动方式
int x,y;//记录当前0所在位置的坐标
int a[9];//九宫格数组
int gox[4]={0,0,1,-1};//x移动方式
int goy[4] = {1,-1,0,0};//y移动方式
char go[5] = "udrl";//移动命令
int flag = 0;//判断是否已经求出解
int judge(){//转换为9位数
return a[8]100000000+a[7]10000000+a[6]1000000+a[5]100000+a[4]10000+a[3]1000+a[2]100+a[1]10+a[0];
}
void trans(int re){//9位数翻译回3*3棋盘
if(re==0)return ;
for(int i = 0;i<=8;i++){
a[i] = re%10;
if(a[i]==0){x = i/3;y=i%3;}
re/=10;
}
}
void bfs(){//广搜
int n;//判断并记录队首元素
while(flag==0){
n = all.front();
all.pop();
}
else n = 0;
for(int i=0;i<4;i++){
trans(n);
int tx = x+gox[i];//移动x
int ty = y+goy[i];//移动y
if(tx>=0&&tx<3&&ty>=0&&ty<3){
//cout<<judge()<<endl;
int temp1 = judge();//储存变化前状态的9位数
int temp = a[tx3+ty];
a[tx3+ty] = 0;
a[x*3+y] = temp;
x = tx;
y = ty;
if(line[judge()]==1)continue;
else{
line[judge()] = 1;
all.push(judge());//入队
distance1[judge()] = distance1[temp1] + 1;//距离增加
gogo[judge()] = gogo[temp1] + go[i];//移动方式更新
if(judge()==result){cout<<gogo[judge()]<<endl;cout<<distance1[judge()]<<endl;flag = 1;return;}
}
}
}
}
}
int main(){
int now;
for(int i=0;i<9;i++){cin>>a[i];if(a[i]==0){x=i/3;y=i%3;}}
for(int i=0;i<9;i++){cin>>now;result+=now*pow(10,i);}
distance1[judge()] = 0;//初始化距离
gogo[judge()] = "";//初始化移动方式位空
cout<<judge()<<endl;
cout<<result<<endl;
bfs();
return 0;
}
