BFS 训练的好题
在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。
输入#1
283104765
输入#2
4
using namespace std;
map<string,int>vis;
struct node{
string s;
int t;
node(){};
node(string a,int b){
s=a;
t=b;
}
};
queue<node>q;
bool BFS(){
while(q.size()){
node u = q.front();
q.pop();
if(u.s=="123804765"){
cout<<u.t;
return true;
}
string s=u.s;
for(int i=0;i<9;i++){
if(s[i]=='0')
{
if(i>=3&&i<=8){//向上拓展
swap(s[i],s[i-3]);
if(s=="123804765"){
cout<<u.t+1<<endl;
return true;
}
if(vis[s]==0){
vis[s]=1;
q.push(node(s,u.t+1));
}
swap(s[i],s[i-3]);
}
if(i>=0&&i<=5)//向下拓展
{
swap(s[i],s[i+3]);
if(s=="123804765"){
cout<<u.t+1<<endl;
return true;
}
if(vis[s]==0){
vis[s]=1;
q.push(node(s,u.t+1));
}
swap(s[i],s[i+3]);
}
if(i%3==1||i%3==2)//向左拓展
{
swap(s[i],s[i-1]);
if(s=="123804765"){
cout<<u.t+1<<endl;
return true;
}
if(vis[s]==0){
vis[s]=1;
q.push(node(s,u.t+1));
}
swap(s[i],s[i-1]);
}
if(i%3==1||i%3==0)//向右拓展
{
swap(s[i],s[i+1]);
if(s=="123804765"){
cout<<u.t+1<<endl;
return true;
}
if(vis[s]==0){
vis[s]=1;
q.push(node(s,u.t+1));
}
swap(s[i],s[i+1]);
}
break;
}
}
} return false;
}
int main(){
string s;
cin>>s;
q.push(node(s,0));
vis[s]=1;
if(!BFS()){
cout<<-1;
}
return 0;
}