IDA* AcWing 181. 回转游戏

﹏ヽ暗。殇╰゛Y 2024-04-07 12:21 71阅读 0赞

## IDA\* AcWing 181. 回转游戏 ##

### 原题链接 ###

[AcWing 181. 回转游戏][AcWing 181.]

### 算法标签 ###

搜索 IDA\*

### 思路 ###

本题采用 IDA\* 算法，即迭代加深的 A\* 算法。

估价函数：

统计中间8个方格中出现次数最多的数出现了多少次，记为  k k k 次。  
每次操作会从中间8个方格中移出一个数，再移入一个数，所以最多会减少一个不同的数。  
因此估价函数可以设为  8 − k 8−k 8−k。  
剪枝：

记录上一次的操作，本次操作避免枚举上一次的逆操作。对于操作的枚举， 使用数字0-7表示操作 A − H A-H A−H  
![在这里插入图片描述][5eafc65d4093477d8eabd2a143d9e66c.png]

如何保证答案的字典序最小？

由于最短操作步数是一定的，因此每一步枚举时先枚举字典序小的操作即可。  
时间复杂度  
假设答案最少需要  k k k 步，每次需要枚举  7 7 7 种不同操作（除了上一步的逆操作），因此最坏情况下需要枚举  7 k 7k 7k 种方案。但加入启发函数后，实际枚举到的状态数很少。  
[摘自AcWing 181. 回转游戏y总题解][AcWing 181. _y]

### 代码 ###

/*
          0     1
          2     3
    4  5  6  7  8  9  10
          11    12
    13 14 15 16 17 18 19
          20    21
          22    23
    */
    
    #pragma GCC optimize(2)
    #pragma GCC optimize(3)
    #include<bits/stdc++.h>
    #define int long long
    #define x first
    #define y second
    #define ump unordered_map
    #define pq priority_queue
    #define rep(i, a, b) for(int i=a;i<b;++i)
    #define Rep(i, a, b) for(int i=a;i>b;--i)
    using namespace std;
    typedef pair<int, int> PII;
    const int N=25;
    //int t, n, m, cnt, ans; 
    int q[N];
    int op[8][7]={
        {0, 2, 6, 11, 15, 20, 22},
        {1, 3, 8, 12, 17, 21, 23},
        {10, 9, 8, 7, 6, 5, 4},
        {19, 18, 17, 16, 15, 14, 13},
        {23, 21, 17, 12, 8, 3, 1},
        {22, 20, 15, 11, 6, 2, 0},
        {13, 14, 15, 16, 17, 18, 19},
        {4, 5, 6, 7, 8, 9, 10}
    };
    // 操作0的互斥操作为操作5 即oppsite[0]=5 操作1的互斥操作为操作4 即oppsite[1]=4
    int oppsite[8]={5, 4, 7, 6, 1, 0, 3, 2};
    // 棋盘最中间的 8 个格子里的数字编号
    int cen[8]={6, 7, 8, 11, 12, 15, 16, 17};
    // 搜索（操作）路径
    int path[100];
    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(){
    	// 设置为静态变量 节省每次变量创建时间
        static int sum[4];
        memset(sum, 0, sizeof sum);
        rep(i, 0, 8){
        	// 统计数字1， 2， 3出现次数
            sum[q[cen[i]]]++;
        }
        int maxv=0;
        rep(i, 1, 4){
            maxv=max(maxv, sum[i]);
        }
        // 最少需要8-maxv操作
        return 8-maxv;
    }
    // 数字平移操作
    void operate(int x){
        int t=q[op[x][0]];
        rep(i, 0, 6){
            q[op[x][i]]=q[op[x][i+1]];
        }
        q[op[x][6]]=t;
    }
    // last 存储最近一次操作 
    bool dfs(int d, int md, int last){
        if(d+f()>md){
            return false;
        }
        if(f()==0){
            return true;
        }
        rep(i, 0, 8){
        	// last!=oppsite[i] 非互斥操作
            if(last!=oppsite[i]){
                operate(i);
                path[d]=i;
                if(dfs(d+1, md, i)){
                    return true;
                }
                operate(oppsite[i]);
            }
        }
        return false;
    }
    signed main(){
    	ios::sync_with_stdio(false);
    	cin.tie(0);
    	cout.tie(0);
    	while(q[0]=rd(), q[0]){
    	    rep(i, 1, 24){
    	        q[i]=rd();
    	    }
    	    int d=0;
    	    while(!dfs(0, d, -1)){
    	        d++;
    	    }
    	    if(!d){
    	        printf("No moves needed");
    	    }else{
    	        rep(i, 0, d){
    	            printf("%c", 'A'+path[i]);
    	        }
    	    }
    	    // 中间 8 个格子里的数字
    	    printf("\n%lld\n", q[6]);
    	}
    	return 0;
    }

参考文献  
[AcWing 181. 回转游戏y总题解][AcWing 181. _y]  
[AcWing 181. 回转游戏（算法提高班）y总视频讲解][AcWing 181. _y 1]

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

[AcWing 181.]: https://www.acwing.com/problem/content/183/
[5eafc65d4093477d8eabd2a143d9e66c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/89f281b063cc48dea605e7118512fedc.png
[AcWing 181. _y]: https://www.acwing.com/solution/content/4056/
[AcWing 181. _y 1]: https://www.acwing.com/video/486/
[9cb4cb80a18345158f8a69e2f196e5b9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/c9b7a8c4ebc048af8e0e460983c3d513.png