E. 杰哥闯稻妻

题解

​ 是一道写起来很烦的搜索题

​ 题目保证最多 $1010$ 次操作内肯定可以将所有方块朝向同一方向，$5^{10}=9,765,625\approx 10^{7}5^\{10\}\; =\; 9,765,625\; \approx \; 10^7$，于是这题直接搜索即可。至于题目要求答案序列字典序最小，在搜索枚举要攻击的方块时从左到右枚举就行(应该也不会有人从右到左qwq)。

​ 题目的数据无论 bfs 还是 dfs 都是可以过的。这题写起来比较烦人的地方应该是进行操作时对状态的修改(至少我是这样)

std

bfs 做法：

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
// 因为C++中有个啥名字也是prev，所以加上这个不然编译报错
#define prev pre_state

// 将5个方块的状态转化为10进制数处理，当然转化为4进制更"压缩"一点
// tran[i][j]表示状态 i 攻击第 j 个方块后的状态
int trans[33333+10][5];
// pref[i]表示bfs中产生状态 i 的前置状态，用于回溯操作
int prev[33333+10];
int ans[2022], tot;
queue<int>que;

void init()
{
    // 先对trans进行初始化
    int a[5], b[5];
    for(a[0]=0; a[0]<4; a[0]++){
        for(a[1]=0; a[1]<4; a[1]++){
            for(a[2]=0; a[2]<4; a[2]++){
                for(a[3]=0; a[3]<4; a[3]++){
                    for(a[4]=0; a[4]<4; a[4]++){
                        // 枚举当前状态
                        int val = a[0]*10000 + a[1]*1000 + a[2]*100 + a[3]*10+ a[4];
                        // 计算攻击第 i 个方块后的状态
                        for(int i=0;i<5;i++){
                            b[i] = ( a[i] + 1 )%4; // 第 i 个
                            b[(i+1)%5] = ( a[(i+1)%5] + 1 )%4; //相邻的 
                            b[(i+2)%5] = a[(i+2)%5];
                            b[(i+3)%5] = a[(i+3)%5];
                            b[(i+4)%5] = ( a[(i+4)%5] + 1 )%4; //相邻的
                            int nxt = b[0]*10000 + b[1]*1000 + b[2]*100 + b[3]*10 + b[4];
                            trans[val][i] = nxt;
                        }
                    }
                }
            }
        }
    }
}

void bfs(int s)
{
    // 这里就是普通的bfs了
    while( !que.empty() )que.pop();
    for(int i=0;i<=33333;i++)prev[i] = -1;
    que.push(s);
    while( !que.empty() ){
        int cur = que.front(); que.pop();
        for(int i=0;i<5;i++){
            int nxt = trans[cur][i];
            if( prev[nxt] == -1 ){ // 这里的prev也可以当做vis数组用
                prev[nxt] = cur;
                que.push( nxt );
                if( nxt == 33333 )return ;
            }
        }
    }
    return ;
}

// 通过prev回溯操作
void dfs(int k,int Start)
{
    if( k == Start )return ;
    dfs( prev[k], Start );
    for(int i=0;i<5;i++){
        // 看前置状态攻击哪一个方块会到达当前状态k 
        if( trans[prev[k]][i] == k ){ ans[tot++] = i; break; }
    }
    return ;
}

int main()
{
    init();

    int a[5];
    for(int i=0;i<5;i++)scanf("%d",a+i);

    for(int i=0;i<5;i++)a[i]--;

    int Start = a[0]*10000 + a[1]*1000 + a[2]*100 + a[3]*10 + a[4];

    bfs( Start );

    tot=0;
    dfs(33333,Start);

    printf("%d\n",tot);
    for(int i=0;i<tot;i++){
        if(i > 0 )printf(" ");
        printf("%d",ans[i]+1);
    }
    printf("\n");

    return 0;
}

dfs 做法：

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;

int stk[20]; // 记录 dfs 过程中的进行的操作序列
int ans[20],tot; // 记录(当前)最优答案
int a[10];

void dfs(int k){
    if( k > 10 || k > tot )return ; // 一个小小的剪枝
    bool flag = true; // 判断是否全都朝向 ‘4’ 面
    for(int i=0;i<5;i++){
        if( a[i] != 4 )flag = false;
    }
    if( flag && k < tot ){ // 如果是一个更优解，则更新ans数组
        for(int i=0;i<k;i++)ans[i] = stk[i];
        tot = k;
        return ;
    }

    for(int i=0;i<5;i++){
        // 攻击第 i 个方块，修改状态
        int x = (i+1)%5, y = (i-1+5)%5;
        a[i] = (a[i] == 4 ? 1 : a[i]+1);
        a[x] = (a[x] == 4 ? 1 : a[x]+1);
        a[y] = (a[y] == 4 ? 1 : a[y]+1);
        stk[k] = i; // 记录当前操作
        dfs( k+1 );
        // 复原
        a[i] = (a[i] == 1 ? 4 : a[i]-1);
        a[x] = (a[x] == 1 ? 4 : a[x]-1);
        a[y] = (a[y] == 1 ? 4 : a[y]-1);
    }
}

int main()
{
    for(int i=0;i<5;i++)scanf("%d",a+i);

    tot = 20;
    dfs(0);

    printf("%d\n",tot);
    for(int i=0;i<tot;i++){
        if(i > 0 )printf(" ");
        printf("%d",ans[i]+1);
    }
    printf("\n");
    return 0;
}