CodeVS/1225

摘要

题目链接	难度等级	完成状态	完成分数	最后编辑时间	失误原因（初次提交分数）
八数码难题	★☆☆☆☆	答案正确	100	2015-8-2 20:02:15	忘记判重（20）

题解

• 由于数据量不大（容易知道最多9!=362880种状态），所以直接bfs找出最近的答案即可，注意判重（用map即可），不需要启发式搜索。

代码

#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();
    }
}