• AcWing 845.八数码


    原题链接

    题解

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

    解决方式

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

    图示

    代码如下

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

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

  • 相关阅读:
    Redis简单案例(二) 网站最近的访问用户
    Redis简单案例(一) 网站搜索的热搜词
    Basic Tutorials of Redis(9) -First Edition RedisHelper
    Basic Tutorials of Redis(8) -Transaction
    Basic Tutorials of Redis(7) -Publish and Subscribe
    Basic Tutorials of Redis(6)
    Basic Tutorials of Redis(5)
    Basic Tutorials of Redis(4) -Set
    Basic Tutorials of Redis(3) -Hash
    Basic Tutorials of Redis(2)
  • 原文地址:https://www.cnblogs.com/Lngstart/p/13203929.html
一二三 - 开发者的网上家园