UVA1343 The Rotation Game旋转游戏

题目：如题，棋盘上由数字1，2，3组成，往A,B,C,D,E,F,G,H8个方向旋转棋盘，使得中间8个数相等，最多有几步。

分析：这题关键在于最大深度的判断，有几个不等数字，就说明至少还需要移动几次，还有一个关键地方就是映射，将8个方向的旋转映射到一维数组。

   00 01
   02 03
04 05 06 07 08 09 10
   11 12
13 14 15 16 17 18 19
   20 21
   22 23

A：0, 2, 6,11,15,20,22

B：1, 3, 8,12,17,21,23

C：10, 9, 8, 7, 6, 5, 4

D：19,18,17,16,15,14,13

E就等于B的反方向，下面同理。

#include<cstdio>
#include<cstring>
#include<cctype>
#include<queue>
#include<iostream>
#include<vector>
#include<list>
using namespace std;

/* 
	      00      01
	      02      03
        04 05 06 07 08 09 10
	      11     12
        13 14 15 16 17 18 19
	      20      21
	      22      23
*/
int line[4][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
};
int center[8] = { 6,7,8,11,12,15,16,17 };
int mp[24];
char ans[10000];
bool isfinal() {
	for (int i = 1; i < 8; i++) {
		if (mp[center[i]] != mp[center[0]]) {
			return false;
		}
	}
	return true;
}
void move(int k) {
	if (k < 4) {
		int temp = mp[line[k][0]];
		for (int i = 0; i < 6; i++)mp[line[k][i]] = mp[line[k][i + 1]];
		mp[line[k][6]] = temp;
	}
	else {
		if (k % 2==0)k -= 3;
		else k -= 5;
		int temp = mp[line[k][6]];
		for (int i = 6; i > 0; i--)mp[line[k][i]] = mp[line[k][i - 1]];
		mp[line[k][0]] = temp;
	}
}
int diff(int t) {
	int ans = 0;
	for (int i = 0; i < 8; i++) {
		if (mp[center[i]] != t)ans++;
	}
	return ans;
}
int h() {
	return min(min(diff(1), diff(2)), diff(3));
}
int dfs(int dep,int maxd) {
	if (isfinal()) { 
		for (int i = 0; i < dep; i++)cout << ans[i];
		cout << endl;
		return true; 
	}
	//最大深度判断
	if (dep + h() > maxd)return false;
	for (int i = 0; i < 8; i++) {
		ans[dep] = 'A' + i;
		move(i);
		if (dfs(dep + 1, maxd))return true;
		int k = 0;
		if (i < 4)if (i % 2 == 0)k = i + 5; else k = i + 3;
		else { if (i % 2 == 0)k = i - 3; else k = i - 5; }
		move(k);//还原
	}
	return false;
}
int main() {
	while (cin >> mp[0] && mp[0]) {
		for (int i = 1; i < 24; i++)cin >> mp[i];
		for (int i = 0; i < 24; i++)if (!mp[i])return 0;
		if(isfinal()) {
			printf("No moves needed\n");
		}
		else {
			for (int maxd = 1; ; maxd++)
				if (dfs(0, maxd)) break;
		}
		printf("%d\n", mp[6]);
	}
	//system("pause");
	return 0;
}

UVA1343 The Rotation Game旋转游戏

相关推荐