D3-八数码
- 题目描述
- 解题思路
- 代码如下
题目描述
解题思路
本题若直接在3*3网格中思考较为困难,可以转换为一维的字符串,在一维字符串中考虑较为简单,要注意本题中两个字符交换位置时只能是x和另外字符交换,本题另外一个难点在于如何维护一个距离数组用于表示交换的次数(可用map,代码中会有注释)
代码如下
#include<bits/stdc++.h>
using namespace std;
unordered_map<string,int> dist;//维护一个从开始状态到结束状态的转换次数
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};//上下左右移动的数轴,dx是左右移动,dy是上下移动
string s1="12345678x";//最终状态,用于和中间状态进行比较
int bfs(string s)
{
queue<string> q;
q.push(s);
dist[s]=0;//刚开始是转换次数为0
while(q.size())
{
string f=q.front();
q.pop();
int distance = dist[f];//将这个状态的转换次数存起来,因为下面会交换元素位置
if(f==s1) return distance;
int k=f.find('x');
int x=k/3,y=k%3;//将s中的元素的一维位置转换为3*3的位置元素
for(int i=0;i<4;i++)
{
int a=x+dx[i],b=y+dy[i];
if(a>=0&&a<3&&b>=0&&b<3)
{
swap(f[k],f[a*3+b]);//再将3*3中的位置转换为s中的一维位置
if(!dist.count(f))
{
dist[f] = distance+1;
q.push(f);
}
swap(f[k],f[a*3+b]);//转换完之后要再转回来
}
}
}
return -1;
}
int main()
{
string s;
char c;
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
{
cin>>c;
s+=c;
}
cout<<bfs(s)<<endl;
return 0;
}