hdu 4531吉哥系列故事之乾坤大挪移

hdu 4531吉哥系列故事之乾坤大挪移2014-03-17 csdn博客 shuangde800题目链接：

http://acm.hdu.edu.cn/showproblem.php？pid=4531

这道搜索题挺恶心的。。。比赛时没有写出来。

首先要解决的问题是怎样判断符合条件的状态，即所有一样的颜色是连在一起的。我是采用最简单也最搓的方法，按上下左右顺序给每一个小三角形标号1～36，然后建立一张邻接矩阵图，然后bfs判断。

然后就是主要的暴力枚举部分，每次有 12种状态转移的选择，开始时用dfs，但爆栈了。然后改成bfs，又各种TLE。然后就是不断地优化优化。

判重的状态可以用一个整数来表示。

矩阵初始标号为：

1 2 3

4 5 6

7 8 9

那么它的状态就是123456789. 采用哈希判断方法。

代码：

#include<cstdio>#include<cstring>#include<vector>#include<cctype>using namespace std; typedef int int64; const int HashSize = 1000003; // 哈希值尺寸，视情况而定const int MaxState = 400000; // 共需要存多少个const int MAXQUE = 500000; intg[40][40];intmat[3][3];char str[12][6];bool vis[40], alpha[150];bool isCol[3], isRow[3];intans;vector<int>G[40];template<typename Type>class Hash{public:void init（）{rear=1;memset（head, -1, sizeof（head））;memset（state, -1, sizeof（state））;} int insert（Type s）{int h = hash（s）, u = head[h];while（u！=-1）{if（state[u] == s） return u; //返回所在位置u = next[u];}state[rear] = s;next[rear] = head[h];head[h] = rear++;return rear-1;// 返回新插入的位置}int find（Type s）{int h = hash（s）, u = head[h];while（u！=-1）{if（state[u] == s） return u; //返回所在位置u = next[u];}return 0;} private:int hash（Type x）{int d = （（x&0x7fffffff）%HashSize）;return d;}private:int head[HashSize], next[MaxState], rear;Type state[MaxState];};Hash<int64>hash;inline void init（）; struct Node{int st;int cnt;}Q[MAXQUE];int que[100];char s[40];inline bool bfs（int st）{int pos=35;while（st>0）{int p = st%10;for（int k=3; k>=0; --k） s[pos--] = str[p][k];st /= 10;}memset（alpha, 0, sizeof（alpha））;memset（vis, 0, sizeof（vis））; for（int i=0; i<36; ++i）if（！vis[i+1]）{if（alpha[s[i]]） return false;vis[i+1] = true;int front=0, rear=1;que[0] = i+1;while（front < rear）{int u = que[front++];for（int j=0; j<G[u].size（）; ++j）{int v = G[u][j];if（！vis[v] && s[v-1]==s[u-1]）{vis[v] = true;que[rear++] = v;}}}alpha[s[i]] = true;}return true;} char buf[15];inline int rotateRow（int st, int row）{sprintf（buf, "%d", st）;char tmp = buf[row*3];buf[row*3] = buf[row*3+1];buf[row*3+1] = buf[row*3+2];buf[row*3+2] = tmp;sscanf（buf, "%d", &st）;return st;}inline int rotateCol（int st, int col）{sprintf（buf, "%d", st）;char tmp = buf[col];buf[col] = buf[3+col];buf[3+col] = buf[6+col];buf[6+col] = tmp;sscanf（buf, "%d", &st）;return st;} inline void solve（）{Q[0].st = 123456789;Q[0].cnt = 0;int front=0, rear=1;hash.insert（Q[0].st）;while（front < rear）{const Node& q = Q[front++]; if（bfs（q.st））{ans = q.cnt;return ;} int st;for（int i=0; i<3; ++i）{if（！isRow[i]） {st = rotateRow（q.st, i）;if（！hash.find（st））{hash.insert（st）;Q[rear].st = st;Q[rear++].cnt = q.cnt+1;} st = rotateRow（st, i）;if（！hash.find（st））{hash.insert（st）;Q[rear].st = st;Q[rear++].cnt = q.cnt+1;}}if（！isCol[i]）{st = rotateCol（q.st, i）;if（！hash.find（st））{hash.insert（st）;Q[rear].st = st;Q[rear++].cnt = q.cnt+1;} st = rotateCol（st, i）;if（！hash.find（st））{hash.insert（st）;Q[rear].st = st;Q[rear++].cnt = q.cnt+1;}}}}} int main（）{int T, cas=1;init（）;scanf（"%d", &T）; while（T--）{int idx=1;memset（isRow, 0, sizeof（isRow））;memset（isCol, 0, sizeof（isCol））;for（int i=0; i<3; ++i）{for（int j=0; j<3; ++j）{char& ch = str[idx][0];ch = getchar（）;while（！isalpha（ch）） ch=getchar（）;for（int k=1; k<5; ++k） str[idx][k] = getchar（）;if（str[idx][4] == "1"） isRow[i]=isCol[j]=true;mat[i][j] = idx++;}} hash.init（）;ans = 100000000;solve（）;printf（"Case #%d: %d
",cas++, ans）; } return 0;} // =============================inline void init（）{memset（g, 0, sizeof（g））;g[1][3]=1, g[1][4]=1, g[5][7]=1, g[5][8]=1, g[9][11]=1, g[9][12]=1, g[13][2]=1, g[13][15]=1, g[13][16]=1, g[17][6]=1, g[17][19]=1, g[17][20]=1, g[21][10]=1, g[21][23]=1, g[21][24]=1, g[25][14]=1, g[25][27]=1, g[25][28]=1, g[29][18]=1, g[29][31]=1, g[29][32]=1, g[33][22]=1, g[33][35]=1, g[33][36]=1,g[2][3]=1, g[2][4]=1, g[2][13]=1, g[6][7]=1, g[6][8]=1, g[6][17]=1, g[10][11]=1, g[10][12]=1, g[10][21]=1, g[14][15]=1, g[14][16]=1, g[14][25]=1, g[18][19]=1, g[18][20]=1, g[18][29]=1, g[22][23]=1, g[22][24]=1, g[22][33]=1, g[26][27]=1, g[26][28]=1, g[30][31]=1, g[30][32]=1, g[34][35]=1, g[34][36]=1,g[3][1]=1, g[3][2]=1, g[15][13]=1, g[15][14]=1, g[27][25]=1, g[27][26]=1, g[7][6]=1, g[7][5]=1, g[7][4]=1, g[19][18]=1, g[19][17]=1, g[19][16]=1, g[31][30]=1, g[31][29]=1, g[31][28]=1, g[11][10]=1, g[11][9]=1, g[11][8]=1, g[23][22]=1, g[23][21]=1, g[23][20]=1, g[35][34]=1, g[35][33]=1, g[35][32]=1, g[4][2]=1, g[4][1]=1, g[4][7]=1, g[16][14]=1, g[16][13]=1, g[16][19]=1, g[28][26]=1, g[28][25]=1, g[28][31]=1, g[8][6]=1, g[8][5]=1, g[8][11]=1, g[20][18]=1, g[20][17]=1, g[20][23]=1, g[32][30]=1, g[32][29]=1, g[32][35]=1, g[12][10]=1, g[12][9]=1, g[24][22]=1, g[24][21]=1, g[36][34]=1, g[36][33]=1; for（int i=1; i<=36; ++i）{G[i].clear（）;for（int j=1; j<=36; ++j）if（g[i][j]）{G[i].push_back（j）;}}}