A* AcWing 179. 八数码

红太狼 2024-04-07 10:10 76阅读 0赞

## A\* AcWing 179. 八数码 ##

### 原题链接 ###

[AcWing 179. 八数码][AcWing 179.]

### 算法标签 ###

搜索 A\* 哈希 康托展开

### 思路 ###

做法：  
引入一个估值函数，用来估计某个点到达终点的距离。  
记f是估值函数，g是真实值，那么f(state) <= g(state)，越接近越好（当估值是0时，类似于Dijkstra算法）  
记dist是从起点到state状态的步数；  
利用的是优先队列，排序依据是dist\[state\] + f(state)  
![在这里插入图片描述][59e472d1220f4b89b22d918f632460a6.png]

具体思路

### 代码 ###

#include<bits/stdc++.h>
    #define int long long
    #define rep(i, a, b) for(int i=a;i<b;++i)
    #define Rep(i, a, b) for(int i=a;i>b;--i)
    #define x first
    #define y second
    #define ump unordered_map
    #define pq priority_queue
    using namespace std;
    typedef pair<int, int> PII;
    inline int rd(){
       int s=0,w=1;
       char ch=getchar();
       while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
       while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
       return s*w;
    }
    void put(int x) {
        if(x<0) putchar('-'),x=-x;
        if(x>=10) put(x/10);
        putchar(x%10^48);
    }
    //估计函数
    int f(string s){
        int res=0;
        rep(i, 0, s.size()){
        	//字符转换为对应下标
            if(s[i]!='x'){
                int t=s[i]-'1';
                //曼哈顿距离 理想条件下最少需要移动距离
                res+=abs(i/3-t/3)+abs(i%3-t%3);
            }
        }
        return res;
    }
    string bfs(string s){
    	// dx方向数组与c方向数组须保持一致
        int dx[4]={-1, 0, 1, 0}, dy[4]={0, 1, 0, -1};
        char c[4]={'u', 'r', 'd', 'l'};
        // 最终状态
        string end="12345678x";
        // 小根堆,按状态的估计终点距离从小到大排序
        ump<string, int> d;
        //存储当前状态由何状态,经过何操作得来
        ump<string, pair<string, char>> prev;
        pq<pair<int, string>, vector<pair<int, string>>, greater<pair<int, string>>> heap;
        heap.push({f(s), s});
        d[s]=0;
        while(heap.size()){
            auto t=heap.top();
            heap.pop();
            string s=t.second;
            if(s==end){
                break;
            }
            int cnt=d[s];
            int xx, yy;
            rep(i, 0, s.size()){
                if(s[i]=='x'){
                    xx=i/3, yy=i%3;
                    break;
                }
            }
            string sour=s;
            rep(i, 0, 4){
                int xxx=xx+dx[i], yyy=yy+dy[i];
                if(xxx>=0&&xxx<3&&yyy>=0&&yyy<3){
                	//交换下标位置
                    swap(s[xx*3+yy], s[xxx*3+yyy]);
                    if(!d.count(s)||d[s]>cnt+1){
                        d[s]=cnt+1;
                        prev[s]={sour, c[i]};
                        heap.push({d[s]+f(s), s});
                    }
                    //恢复下标位置
                    swap(s[xx*3+yy], s[xxx*3+yyy]);
                }
            }
        }
        // res存储反向交换过程
        string res;
        while(end!=s){
        // 结尾逆向输出交换过程
            res+=prev[end].y;
            end=prev[end].x;
        }
        // 由于res存储反向交换过程 需要经行翻转得到正向交换过程
        reverse(res.begin(), res.end());
        return res;
    }
    signed main(){
        ios::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        string g, c, seq;
        while(cin>>c){
            g+=c;
            if(c!="x"){
                seq+=c;
            }
        }
        int t=0;
        rep(i, 0, seq.size()){
            rep(j, i+1, seq.size()){
                if(seq[i]>seq[j]){
                    t++;
                }
            }
        }
        // 八数码无解  
        if(t%2){
            puts("unsolvable");
        }else{
            cout<<bfs(g);
        }
        return 0;
    }

参考文献  
[AcWing 179. 八数码][AcWing 179. 1]

原创不易  
转载请标明出处  
如果对你有所帮助 别忘啦点赞支持哈  
![在这里插入图片描述][9cb4cb80a18345158f8a69e2f196e5b9.png]

[AcWing 179.]: https://www.acwing.com/problem/content/181/
[59e472d1220f4b89b22d918f632460a6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/918743cb422943249ea0601750d42be4.png
[AcWing 179. 1]: https://www.acwing.com/solution/content/15289/
[9cb4cb80a18345158f8a69e2f196e5b9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/df108f4fa87e4b2f8fc0618a21c87f5f.png