（以“分类:广度优先搜索 ==摘要== {{信息题|八数码难题|http://www.codevs.cn/problem/1225/|1|100|忘记判重|20|time=2015-8-2 20:02:15}} ==题解== *...”为内容创建页面） |
小 （补充细节） |
||
| 第3行： | 第3行： | ||
{{信息题|八数码难题|http://www.codevs.cn/problem/1225/|1|100|忘记判重|20|time=2015-8-2 20:02:15}} | {{信息题|八数码难题|http://www.codevs.cn/problem/1225/|1|100|忘记判重|20|time=2015-8-2 20:02:15}} | ||
==题解== | ==题解== | ||
| − | *由于数据量不大（容易知道最多9!= | + | *由于数据量不大（容易知道最多9!=362880种状态），所以直接bfs找出最近的答案即可，注意判重（用map即可），不需要启发式搜索。 |
==代码== | ==代码== | ||
<pre>#include<cstdio> | <pre>#include<cstdio> | ||
| 题目链接 | 难度等级 | 完成状态 | 完成分数 | 最后编辑时间 | 失误原因（初次提交分数） |
|---|---|---|---|---|---|
| 八数码难题 | ★☆☆☆☆ | 答案正确 | 100 | 2015-8-2 20:02:15 | 忘记判重（20） |
CloudLunar#include<cstdio>
#include<string>
#include<iostream>
#include<queue>
#include<climits>
#include<map>
using namespace std;
//将字符串中的index 通过坐标加减 获取到新的位置//
inline int getPoint(int p,int dx,int dy)
{
int x=p/3+1+dx,y=p%3+1+dy;
return (x>0&&y>0&&x<=3&&y<=3)? 3*(x-1)+y-1 : -1;
}
//获取下一个index//
const int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
string next(string str,int d)
{
int zero=str.find('0'),got=getPoint(zero,dx[d],dy[d]);
if(d==-1)return "";
swap(str[zero],str[got]);
return str;
}
map<string,int> Dis;
queue<string> p;
int main()
{
string from;
cin>>from;
p.push(from);
//Bfs广搜//
Dis[from]=0;
while(!p.empty())//队列非空//
{
for(int i=0;i<=3;++i)//扩展下一个位置//
{
string nextStr=next(p.front(),i);
//判重和无效(一开始忘记判重了- -不好意思)//
if(nextStr==""||Dis.count(nextStr))continue;
//更新目标点并入队//
Dis[nextStr]=Dis[p.front()]+1;
p.push(nextStr);
//到达答案//
if(nextStr=="123804765")
{cout<<Dis["123804765"]<<endl;return 0;}
}
p.pop();
}
}