IDA* AcWing 181. 回转游戏
IDA* 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
如何保证答案的字典序最小?
由于最短操作步数是一定的,因此每一步枚举时先枚举字典序小的操作即可。
时间复杂度
假设答案最少需要
k
k
k 步,每次需要枚举
7
7
7 种不同操作(除了上一步的逆操作),因此最坏情况下需要枚举
7
k
7k
7k 种方案。但加入启发函数后,实际枚举到的状态数很少。
摘自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总视频讲解
原创不易
转载请标明出处
如果对你有所帮助 别忘啦点赞支持哈