【问题描述】
在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。
【格式】
输入格式
输入初试状态，一行九个数字，空格用0表示
输出格式
只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数(测试数据中无特殊无法到达目标状态数据)
样例输入1
283104765
样例输出1
4
直接广搜
#include<iostream>
#include<cstdio>
#include<string>
#include<queue>
#include<set>
using namespace std;
const int xx[4]={0,0,1,-1};
const int yy[4]={1,-1,0,0};
struct node
{
string s;
int step;
};
set<string>st;queue<node>q;
string aa="123804765",src;
int ans;
int bfs()
{
node t;
t.s=src;t.step=0;
q.push(t);
st.insert(src);
while(!q.empty())
{
int i;int x,y,x1,y1;
t=q.front();q.pop();
if(t.s==aa) return t.step;
for (i=0;i<=8;i++)
if(t.s[i]=='0') break;
x=i/3,y=i%3;//行，列
for(int j=0;j<=3;j++)
{
x1=x+xx[j];y1=y+yy[j];
if(x1>=0&&x1<=2&&y1>=0&&y1<=2)
{
int k=x1*3+y1;//链
node tt=t;
tt.s[i]=t.s[k];tt.s[k]=t.s[i];
tt.step++;
set<string>::iterator it;
it=st.find(tt.s);
if(it==st.end())
{
q.push(tt);
st.insert(tt.s);
}
}
}
}
}
int main()
{
cin>>src;
ans=bfs();
cout<<ans;
return 0;
}