(以“分类:广度优先搜索 ==摘要== {{信息题|八数码难题|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) |
#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(); } }