八数码难题

题目描述

在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。
棋盘中留有一个空格，空格用0来表示。空格周围的棋子可以移到空格中。
要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。

输入格式

输入初始状态，一行九个数字，空格用0表示

输出格式

只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数(测试数据中无特殊无法到达目标状态数据)

样例 #1

样例输入 #1

283104765

样例输出 #1

4

分析

• 假设初始状态为 a1，目标状态为 an，考虑如何由 a1 经过怎样的路径可以到达为 an，要求路径最短。

• 对于要求最短方案的通常我们会想到bfs，每次向外扩展，第一次扩展到的一定是最短的。

• 这道题目主要是关于问题的转化，一个线性序列的转化，我们可以通过某些计算发现其中的规律
  

• 确定了位置之后，按照上下左右的顺序转移就行了，同时将新生成的 ai，压入队列，步数+1。

• 如果发现目标答案就退出；如果方案枚举完了都没有结果，那就是无解。

#include<bits/stdc++.h>
using namespace std;
int dis[][2]= {-1,0, 1,0, 0,-1, 0,1};
unordered_map<string,int> mp;
string s,u,v,goal="123804765";

int bfs() {
    queue<string> que;
    que.push(s); mp[s]=0; // 到s的步数
    while(que.size()) {
        u=que.front(); que.pop();
        if(u==goal) return mp[u];
        int pa=u.find('0'), x=pa/3, y=pa%3;
        for(int i=0; i<4; i++) {
            int tx=x+dis[i][0], ty=y+dis[i][1], pb=tx*3+ty;
            if(tx<0 || tx>2 ||ty<0 ||ty>2) continue;
            v=u; swap(v[pa], v[pb]); // 转移
            if(!mp.count(v)) mp[v]=mp[u]+1, que.push(v);
        }
    }
    return -1;
}
int main() {
    cin>>s;
    cout<<bfs()<<endl;
    return 0;
}