E. 杰哥闯稻妻
题解
是一道写起来很烦的搜索题
题目保证最多 次操作内肯定可以将所有方块朝向同一方向,,于是这题直接搜索即可。至于题目要求答案序列字典序最小,在搜索枚举要攻击的方块时从左到右枚举就行(应该也不会有人从右到左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;
}