题解 UVA1343 The Rotation Game

题解区都是 \(\text{IDA*}\)，实际上这题 \(\text{A*}\) 也可以，代码也很简单。

Solution

首先由于整个棋盘的形状是已知的，所以我们可以先处理出 \(\text{A~H}\) 操作对应行列的格子编号及中间 \(8\) 个格子的编号，使代码实现简单化。

而对于 \(\text{A*}\)，最重要的就是估价函数 \(f(x)=g(x)+h(x)\)，那么我们可以把每一个棋盘状态 \(x\) 的操作次数当作 \(g(x)\)，然后把中间 \(8\) 个格子中还需要修改的格子数当作估计的 \(h(x)\)，最后以 \(f(x)\) 为序来进行广搜即可。

因为棋盘上只有 \(24\) 个格子，目标状态也是一定能达到的，且时限放到了 \(3s\)，\(\text{A*}\) 算法足以通过此题。

Code

实现非常清晰，加上提前处理的编号也只有 \(50\) 多行

#include<bits/stdc++.h>
using namespace std;
const int p[]={7,8,9,12,13,16,17,18},//中心格子
li[][8]={{1,3,7,12,16,21,23},//A~H操作
		{2,4,9,13,18,22,24},
		{11,10,9,8,7,6,5},
		{20,19,18,17,16,15,14},
		{24,22,18,13,9,4,2},
		{23,21,16,12,7,3,1},
		{14,15,16,17,18,19,20},
		{5,6,7,8,9,10,11}};
struct node{
	int step,f,a[25];
	vector<int>op;//记录每次操作
	inline void init(){step=0;op.clear();}
	inline int h(){//计算需修改的格子数
		int c[4]={0,0,0,0};
		for(int x:p)c[a[x]]++;
		return 8-*max_element(c+1,c+4);
	}inline void calcf(){f=step+h();}
	bool operator<(node x)const{return f==x.f?op>x.op:f>x.f;}
	inline void move(int x){//进行修改操作
		int tmp=a[li[x][0]];
		for(int i=0;i<6;i++)a[li[x][i]]=a[li[x][i+1]];
		a[li[x][6]]=tmp;
	}
}st;
void Astar(){
	st.init();
	st.calcf();
	if(!st.h()){
		printf("No moves needed\n%d\n",st.a[p[0]]);
		return;
	}
	priority_queue<node>q;
	q.push(st);
	while(!q.empty()){
		node u=q.top();q.pop();
		for(int i=0;i<8;i++){
			node v=u;
			v.move(i);v.calcf();
			v.op.push_back(i);
			v.step++;
			if(!v.h()){//v为目标状态，直接输出
				for(int x:v.op)putchar('A'+x);
				printf("\n%d\n",v.a[p[0]]);
				return;
			}q.push(v);
		}
	}
}
int main(){
	while(~scanf("%d",&st.a[1])){
		if(!st.a[1])break;
		for(int i=2;i<=24;i++)scanf("%d",&st.a[i]);
		Astar();
	}
	return 0;
}