首页 > 代码库 > [hdu4801]搜索

[hdu4801]搜索

http://acm.hdu.edu.cn/showproblem.php?pid=4801

状态和生成状态的过程处理好了,这个题就是简单的搜索题了==

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <map> 7 #include <stack> 8 #include <string> 9 #include <ctime>10 #include <queue>11 #define mem0(a) memset(a, 0, sizeof(a))12 #define mem(a, b) memset(a, b, sizeof(a))13 #define lson l, m, rt << 114 #define rson m + 1, r, rt << 1 | 115 #define eps 0.000000116 #define lowbit(x) ((x) & -(x))17 #define memc(a, b) memcpy(a, b, sizeof(b))18 #define x_x(a) ((a) * (a))19 #define LL long long20 #define DB double21 #define pi 3.1415926535922 #define MD 1000000723 #define INF (int)1e924 #define max(a, b) ((a) > (b)? (a) : (b))25 using namespace std;26 int arr[6][12] = {27         {0, 1, 9, 15, 19, 18, 10, 4, 22, 23, 21, 20}, {4, 10, 18, 19, 15, 9, 1, 0, 20, 21, 23, 22},28         {1, 3, 7, 13, 17, 19, 21, 23, 9, 8, 14, 15}, {23, 21, 19, 17, 13, 7, 3, 1, 15, 14, 8, 9},29         {22, 23, 9, 8, 7, 6, 5, 4, 0, 1, 3, 2}, {4, 5, 6, 7, 8, 9, 23, 22, 2, 3, 1, 0},30 };31 int arr2[6][4] = {{0, 1, 2, 3}, {4, 5, 10, 11}, {6, 7, 12, 13}, {8, 9, 14, 15}, {16, 17, 18, 19}, {20, 21, 22, 23}};32 int n, ans;33 struct Node {34         int a[24];35         void inp() {36                 for(int i = 0; i < 24; i++) {37                         scanf("%d", a + i);38                 }39         }40 };41 Node doit(Node state, int arr[])42 {43         Node tmp = state;44         for(int i = 0; i < 8; i++) state.a[arr[i]] = tmp.a[arr[(i + 2) % 8]];//转两格45         for(int i = 0; i < 4; i++) state.a[arr[i + 8]] = tmp.a[arr[(i + 1) % 4 + 8]];//转一格,这里想都没想写成了走两格,wa了无数次,写搜    索题一定要细心啊46         return state;47 }48 int getAns(Node state)49 {50         int ans = 0;51         for(int i = 0; i < 6; i ++) {52                 int F = 1;53                 for(int j = 1; j < 4; j++) {54                         if(state.a[arr2[i][j]] != state.a[arr2[i][j - 1]]) {55                                 F = 0;56                                 break;57                         }58                 }59                 ans += F;60         }61         return ans;62 }63 64 void dfs(int k, Node state)65 {66         if(k > n) return;67         for(int i = 0; i < 6; i++) {68                 Node newState = doit(state, arr[i]);69                 ans = max(ans, getAns(newState));70                 dfs(k + 1, newState);71         }72 }73 int main()74 {75         //freopen("input.txt", "r", stdin);76         //freopen("output.txt", "w", stdout);77         while(cin>> n) {78                 Node state;79                 state.inp();80                 ans = getAns(state);81                 dfs(1, state);82                 cout<< ans<< endl;83         }84         return 0;85 }
View Code

 

[hdu4801]搜索