U455764 The Rotation Game
题目理解
本题要求移动\(A-H\)中的一列或一行,使其整个一行和一列的数字移动,使最后的中间8个的数字相同。求最少需要移动的步数和它的操纵顺序
思路
1.本题可以很显然的想到用 \(BFS\) 来枚举执行不同字母操作后结果,但每 \(BFS\) 一次就会增加八倍最后肯定会爆队列,因此不可用
2.如果 \(BFS\) 不行那 \(DFS\) 行不行,显然是不行的因为最终答案的操纵次数不会太多,但 \(DFS\) 会将一条路径一直走下去(如一直操纵A,然后B……,若答案在后面,则时间复杂度会超)
3.既然答案的深度不深,且 \(BFS\) 又用不了,那自然会想到迭代加深,一层一层的用 \(DFS\) 遍历即可
实现
1. 将 # 字格的格子按从上到下,从左到右进行编号,在将它每一个操作的对应行或列进行打表,方便后面修改
int op[8][7]={
{0,2,6,11,15,20,22}, //A
{1,3,8,12,17,21,23}, //B
{10,9,8,7,6,5,4}, //C
{19,18,17,16,15,14,13}, //D
{23,21,17,12,8,3,1}, //E
{22,20,15,11,6,2,0}, //F
{13,14,15,16,17,18,19}, //G
{4,5,6,7,8,9,10}, //H
};
2. 在定义一个函数来专门执行每一次的操作
void operate(int x){
int t=a[op[x][0]];
for(int i=0;i<6;i++){
a[op[x][i]]=a[op[x][i+1]];
}
a[op[x][6]]=t;
}
3. 因为最后要判断中间的八个数是否相同,因此可以打表将中间八个数编号储存起来;而在 \(DFS\) 中需要回溯,而本题的回溯只需要进行它的逆操作即可(如\(A-F\),\(B-E\))因此需要储存一个逆操作序列。最后再写一个\(check()\)函数来判断中间八个数是否相同。
int cent[8]={6,7,8,11,12,15,16,17};//center
int iop[8]={5,4,7,6,1,0,3,2};
bool check(){
for(int i=1;i<8;i++){
if(a[cent[i]]!=a[cent[0]])return false;
}
return true;
}
4. 最后的最后,套用迭代加深的模板即可
剪枝:估价函数
因为每一次操作最多使一个点变正确,若现在每一次操作都能修正一个,那最少需要\(8-x\)(\(x\)是目前相同个数最多的数字的个数)步才能完成,若当前的预估次数和已经完成的和大于了当前迭代的深度\(dep\)那在搜索下去没有任何用了,可以直接推出
int f(){
static int cnt[5];
memset(cnt,0,sizeof(cnt));
for(int i=0;i<8;i++){
cnt[a[cent[i]]]++;
}
int k(0);
for(int i=1;i<=3;i++)k=max(k,cnt[i]);
return 8-k;
}
最后上完整代码
#include<bits/stdc++.h>
using namespace std;
int op[8][7]={
{0,2,6,11,15,20,22}, //A
{1,3,8,12,17,21,23}, //B
{10,9,8,7,6,5,4}, //C
{19,18,17,16,15,14,13}, //D
{23,21,17,12,8,3,1}, //E
{22,20,15,11,6,2,0}, //F
{13,14,15,16,17,18,19}, //G
{4,5,6,7,8,9,10}, //H
};
int cent[8]={6,7,8,11,12,15,16,17};//center
int iop[8]={5,4,7,6,1,0,3,2};
int dep,a[24],path[110];
void operate(int x){
int t=a[op[x][0]];
for(int i=0;i<6;i++){
a[op[x][i]]=a[op[x][i+1]];
}
a[op[x][6]]=t;
}
bool check(){
for(int i=1;i<8;i++){
if(a[cent[i]]!=a[cent[0]])return false;
}
return true;
}
int f(){
static int cnt[5];
memset(cnt,0,sizeof(cnt));
for(int i=0;i<8;i++){
cnt[a[cent[i]]]++;
}
int k(0);
for(int i=1;i<=3;i++)k=max(k,cnt[i]);
return 8-k;
}
bool dfs(int u,int last){
if(u+f()>dep)return false;
if(check())return true;
for(int i=0;i<8;i++){
if(iop[i]==last)continue;
operate(i);
path[u]=i;
if(dfs(u+1,i))return true;
operate(iop[i]);
}
return false;
}
int main(){
while(cin>>a[0],a[0]){
for(int i=1;i<24;i++)cin>>a[i];
for(dep=0;!dfs(0,-1);dep++);
if(!dep)cout<<"No moves needed";
for(int i=0;i<dep;i++){
cout<<char('A'+path[i]);
}
cout<<endl<<a[6]<<endl;
}
}
标签:11,12,15,U455764,17,16,int,Game,Rotation
From: https://www.cnblogs.com/XichenOC/p/18682331