首页 > 代码库 > [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 }
[hdu4801]搜索
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。