AcWing 181. 回转游戏    原题链接    简单

作者： 作者的头像   yxc ,  2019-08-22 15:06:53 ,  所有人可见 ,  阅读 4343

46


8

算法

(IDA*, DFS) $O(7^k)$

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

估价函数：

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

剪枝：

  • 记录上一次的操作，本次操作避免枚举上一次的逆操作。

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

  • 由于最短操作步数是一定的，因此每一步枚举时先枚举字典序小的操作即可。

时间复杂度

假设答案最少需要 $k$ 步，每次需要枚举 $7$ 种不同操作（除了上一步的逆操作），因此最坏情况下需要枚举 $7^k$ 种方案。但加入启发函数后，实际枚举到的状态数很少。

C++ 代码

/*
      0     1
      2     3
4  5  6  7  8  9  10
      11    12
13 14 15 16 17 18 19
      20    21
      22    23
*/


#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 24;

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}
};
int center[8] = {6, 7, 8, 11, 12, 15, 16, 17};
int opposite[8] = {5, 4, 7, 6, 1, 0, 3, 2};

int path[100];

int f()
{
    static int sum[4];
    memset(sum, 0, sizeof sum);
    for (int i = 0; i < 8; i ++ ) sum[q[center[i]]] ++ ;

    int s = 0;
    for (int i = 1; i <= 3; i ++ ) s = max(s, sum[i]);
    return 8 - s;
}

bool check()
{
    for (int i = 1; i < 8; i ++ )
        if (q[center[i]] != q[center[0]])
            return false;
    return true;
}

void operation(int x)
{
    int t = q[op[x][0]];
    for (int i = 0; i < 6; i ++ ) q[op[x][i]] = q[op[x][i + 1]];
    q[op[x][6]] = t;
}

bool dfs(int depth, int max_depth, int last)
{
    if (depth + f() > max_depth) return false;
    if (check()) return true;

    for (int i = 0; i < 8; i ++ )
    {
        if (opposite[i] == last) continue;
        operation(i);
        path[depth] = i;
        if (dfs(depth + 1, max_depth, i)) return true;
        operation(opposite[i]);
    }

    return false;
}

int main()
{
    while (scanf("%d", &q[0]), q[0])
    {
        for (int i = 1; i < N; i ++ ) scanf("%d", &q[i]);
        int depth = 0;
        while (!dfs(0, depth, -1))
        {
            depth ++ ;
        }
        if (!depth) printf("No moves needed");
        for (int i = 0; i < depth; i ++ ) printf("%c", 'A' + path[i]);
        printf("\n%d\n", q[6]);
    }

    return 0;
}

21 评论

用户头像
Moreality   2021-08-12 23:08      2    踩      回复

这个 check() 没必要吧, 直接f()估价的收如果返回0就是中间8个都为相同的情况了

用户头像
Snow_raw   2022-01-14 23:11         踩      回复

有道理

用户头像
冰_52   2个月前         踩      回复

会更快dfs快一点就会快很多

用户头像
云峰映日晖   8个月前      1    踩      回复

让大家看看我写的丑陋的代码

#include<iostream>
using namespace std;

const int N = 24;
int a[7], b[7], c[7], d[7];
char opc[8]{ 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H' };
int rev_op[8]{ 5, 4, 7, 6, 1, 0, 3, 2 };
char ans[1000];

bool input()
{
    cin >> a[0];
    if (!a[0]) return false;
    cin >> b[0] >> a[1] >> b[1];
    for (int& i : c) cin >> i;
    cin >> a[3] >> b[3];
    for (int& i : d) cin >> i;
    cin >> a[5] >> b[5] >> a[6] >> b[6];
    a[2] = c[2], b[2] = c[4];
    a[4] = d[2], b[4] = d[4];
    return true;
}

int H()
{
    int cnt[4]{};
    ++cnt[a[2]], ++cnt[a[3]], ++cnt[a[4]];
    ++cnt[b[2]], ++cnt[b[3]], ++cnt[b[4]];
    ++cnt[c[3]], ++cnt[d[3]];
    return 8 - max(max(cnt[1], cnt[2]), cnt[3]);
}

void movement(int op)
{
    int tmp;
    switch (op)
    {
    case 0:
        tmp = a[0];
        for (int i = 0; i < 6; ++i) a[i] = a[i + 1];
        a[6] = tmp, c[2] = a[2], d[2] = a[4];
        break;
    case 1:
        tmp = b[0];
        for (int i = 0; i < 6; ++i) b[i] = b[i + 1];
        b[6] = tmp, c[4] = b[2], d[4] = b[4];
        break;
    case 2:
        tmp = c[6];
        for (int i = 6; i > 0; --i) c[i] = c[i - 1];
        c[0] = tmp, a[2] = c[2], b[2] = c[4];
        break;
    case 3:
        tmp = d[6];
        for (int i = 6; i > 0; --i) d[i] = d[i - 1];
        d[0] = tmp, a[4] = d[2], b[4] = d[4];
        break;
    case 4:
        tmp = b[6];
        for (int i = 6; i > 0; --i) b[i] = b[i - 1];
        b[0] = tmp, c[4] = b[2], d[4] = b[4];
        break;
    case 5:
        tmp = a[6];
        for (int i = 6; i > 0; --i) a[i] = a[i - 1];
        a[0] = tmp, c[2] = a[2], d[2] = a[4];
        break;
    case 6:
        tmp = d[0];
        for (int i = 0; i < 6; ++i) d[i] = d[i + 1];
        d[6] = tmp, a[4] = d[2], b[4] = d[4];
        break;
    case 7:
        tmp = c[0];
        for (int i = 0; i < 6; ++i) c[i] = c[i + 1];
        c[6] = tmp, a[2] = c[2], b[2] = c[4];
        break;
    }
}

bool IDA_star(int cur, int pre_op, int limit)
{
    int h = H();
    if (h == 0)
        return true;

    if (cur + h > limit)
        return false;
    for (int i = 0; i < 8; ++i)
    {
        if (rev_op[i] == pre_op) continue;
        ans[cur] = opc[i];
        movement(i);
        if (IDA_star(cur + 1, i, limit))
            return true;
        movement(rev_op[i]);
    }
    return false;
}

void solve()
{
    int limit;
    for (limit = 0;; ++limit)
    {
        if (IDA_star(0, -1, limit))
            break;
    }
    if (limit) for (int i = 0; i < limit; ++i) cout << ans[i];
    else cout << "No moves needed";
    cout << '\n';
    cout << a[2] << '\n';
}

signed main()
{
    while (input())
        solve();
    return 0;
}
用户头像
BT7274   2022-03-28 19:04      1    踩      回复

为甚么这里题解的难度和题目的难度不一样

用户头像
incra   2023-01-09 09:06         踩      回复

后来改难度了吧

用户头像
糖豆   2023-06-27 10:50         踩      回复

这题要是简单，就有点过分了

用户头像
masonpop   2022-12-27 16:09         踩      回复

大佬求助，连样例都过不去

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cmath> 
/* 地图:
      0     1
      2     3
4  5  6  7  8  9  10
      11    12
13 14 15 16 17 18 19
      20    21
      22    23
*/ 
using namespace std;
const int maxn=24;
bool flag=0;
int a[maxn],tmp[5],rp=0;
const int move[maxn][maxn]={//每种操作的序列 
    {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}
};
const int cent[maxn]={6,7,8,11,12,15,16,17};//中间的格子
const int inv[maxn]={5,4,7,6,1,0,3,2};//逆运算
int ans[maxn*maxn];
inline int f()//估价 
{
    memset(tmp,0,sizeof(tmp));
    for(int i=0;i<8;i++)tmp[a[cent[i]]]++;//统计
    int num=0;
    for(int i=1;i<=3;i++)num=max(num,tmp[i]);
    return (8-num); 
} 
inline void modify(int x)//进行操作x
{
    int t=a[move[x][0]];
    for(int i=0;i<=5;i++)a[move[x][i]]=a[move[x][i+1]];
    a[move[x][6]]=t;    
} 
inline void IDA_star(int step,int last,int maxdep)
{
    if(step+f()>maxdep)return;//剪枝
    if(f()==0)
    {
        flag=1;
        return;
    } 
    if(flag)return;
    for(int i=0;i<8;i++)
    {
        if(inv[i]==last)continue;//无意义
        modify(i);
        ans[step]=i;//记录答案
        IDA_star(step+1,i,maxdep);
        modify(inv[i]);//还原 
    }
}
int main()
{
    while(scanf("%d",&a[0]) && a[0])
    {
        for(int i=1;i<=23;i++)scanf("%d",&a[i]);
        flag=0;
        for(rp=0;;rp++)
        {
            IDA_star(0,-1,rp);
            if(flag)break;
        }
        if(!rp)printf("No moves needed\n");
        for(int i=0;i<rp;i++)printf("%c",ans[i]+'A');
        printf("\n%d\n",a[6]);
    }
    return 0;
}
用户头像
Plums   2022-12-24 22:40         踩      回复

为什么y总这个代码用java写就不对了

用户头像
fml4d1   2021-07-11 10:18         踩      回复

y总好厉害

用户头像
lyt666   2020-06-04 11:12         踩      回复

y总，这题为啥用IDA星，A星不行么？

用户头像
yxc   2020-06-09 10:15         踩      回复

应该也可以。IDA*一般比A*好写一点。

用户头像
lyt666   2020-06-09 14:37    回复了 yxc 的评论         踩      回复

嗯呢

用户头像
黄亦玫   2020-10-01 09:04    回复了 yxc 的评论         踩      回复

y总，A*怎么保证输出字典序？？

用户头像
yxc   2020-10-15 14:15    回复了 黄亦玫 的评论         踩      回复

A*算法求字典序比较麻烦，因为优先队列中是按估价函数排序而非字典序排序，所以除非将步数最小的所有方案全部求出，否则是无法求出字典序的。

用户头像
黄亦玫   2020-10-15 14:29    回复了 yxc 的评论         踩      回复

嗯呢，那就是最好用IDA*喽！！

用户头像
yxc   2020-10-15 14:45    回复了 黄亦玫 的评论         踩      回复

对的，本题用IDA*比较好。

用户头像
Z同学   2020-02-16 21:04         踩      回复

yls，sum数组我不加static段错误了，这是为啥啊

用户头像
yxc   2020-02-16 21:47         踩      回复

我试了一下，上面的代码去掉static也可以AC啊。

用户头像
Z同学   2020-02-16 22:01    回复了 yxc 的评论         踩      回复

刚才是我测试错误例子的时候发生的MLE，当时没交，现在直接交AC了，我也不知道为啥......

用户头像
yxc   2020-02-16 22:04    回复了 Z同学 的评论         踩      回复

调试功能对输入长度有限制，不能超过2000个字符。提交功能没有此限制。