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 0102 0304 05 06 07 08 09 1011 1213 14 15 16 17 18 1920 2122 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旋转游戏的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。