AcWing 845.八数码

原题链接

题解

要求最小的交换次数,那么就可以使用bfs来做,可以把每一次的交换之后的图抽象成一个节点,那么每次转移状态就相当于向下一个节点走,走过的边的权重为1(不是在原来的3*3的图上做bfs),这样就可以使用dfs做了
需要解决的问题是:
①每一个状态该如何表示
②如何记录每个状态的距离
③什么情况下表示不能后形成最终的状态

解决方式

①可以把二维数组转化成字符串的形式,每一步形成的字符串就是一个状态(每一个状态不要重复的经过,判定就好)
②因为是使用的字符串表示的状态,以前做bfs的时候,都是单一的点或者是坐标,这里就使用哈希表的方式,将字符串转化成对应的下标(以后这种类似的情况下类比也可以使用哈希表的方式)
③当队列为空了,还是没有找到最终状态,就表示不能够达到这个最终的状态(因为已经将所有的状态枚举了)
接下来就是常规的dfs的过程了,这道题最难的地方就在于上述的几点以及抽象的表示

图示

AcWing 845.八数码

代码如下

#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>

using namespace std;

int bfs(string start){
    string end = "12345678x";//定义最终状态
    queue<string> q;
    unordered_map<string, int> dis;
    int dx[4] = {0, 0, -1, 1}, dy[4] = {1, -1, 0, 0};

    q.push(start); dis[start] = 0;

    while(q.size()){
        auto t = q.front(); q.pop();

        if(t == end) return dis[t];
        int j = t.find(‘x‘);

        for(int i = 0; i < 4; ++i){
            //这里还是转化成二维数组做方便一点,因为直接在字符串中x的左右最近的点不一定能够走到还又要判定
            int x = j / 3 + dx[i], y = j % 3 + dy[i];
            if(x >= 0 && x < 3 && y >= 0 && y < 3){
                string s = t;
                swap(s[x * 3 + y], s[j]);
                if(!dis.count(s)){
                    dis[s] = dis[t] + 1;
                    q.push(s);
                }
            }
        }
    }

    return -1;
}
int main(){
    string start;
    for(int i = 0; i < 9; ++i){
        char ch; cin >> ch;
        start += ch;
    }

    cout << bfs(start) << endl;

    return 0;
}

这个题目中,每一个变化都是代表着一种状态,难在不知道如何表示状态(这里是使用字符串表示每一个图),当把所有的状态枚举结束之后,还是没有出现结果,此时说明了这个输入的初始状态是不能够转化成最终的状态。搜索并不一定要在现有的图上做,如果每一步会改变图,就可以把每一次改变的图抽象成一个结点,用某一种状态去表示,然后结点和结点之间就构成了一张新的图。

AcWing 845.八数码

上一篇:Redis的简介与安装(win)


下一篇:windows+mingw编译CTK框架