解题报告人:SpringWater(GHQ)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4531
记忆化广搜 + 状态压缩:
之前超内存,后来将string字符串改为int型状态,就不超了,但是悲剧的接着超时间。
之前老是超时,后来才发现,是我检查是否合格,我用的矩阵36 * 36广搜的超时,当改为加边法来有选择的广搜之后就AC了
#include <stdio.h> #include <string.h> #include <iostream> #include <queue> #include <string> #include <map> using namespace std; queue<int> que; map<int, int> mmap; queue<int> bque; string s[3][3]; char color[36]; int Map[36][36]; int vis[36]; int two[150]; struct Edge{ int node, next; }edge[36 * 36]; int head[36], len; void add_edge(int a, int b) { edge[len].node = b, edge[len].next = head[a]; head[a] = len++; edge[len].node = a, edge[len].next = head[b]; head[b] = len++; } int bfs() { memset(vis, 0, sizeof(vis)); memset(two, 0, sizeof(two)); for(int i = 0; i < 36; ++i) { if(!vis[i]) { if(two[color[i]]) return 0; two[color[i]] = 1; vis[i] = 1; bque.push(i); while(!bque.empty()) { int now = bque.front(); bque.pop(); for(int j= head[now]; ~j; j = edge[j].next) { if((color[i] == color[edge[j].node]) && !vis[edge[j].node]) vis[edge[j].node] = 1, bque.push(edge[j].node); } } } } return 1; } int ok(int tt) { int cnt = 0; len = 0; char temp[10]; sprintf(temp, "%09d", tt); memset(head, -1, sizeof(head)); for(int i = 0; i < 3; ++i) { for(int j = 0; j < 3; ++j) { int num = temp[i * 3 + j] - '0'; int n = num / 3, m = num % 3; for(int k = 0; k < 4; ++k) color[cnt + k] = s[n][m][k]; add_edge(cnt, cnt + 2); add_edge(cnt, cnt + 3); add_edge(cnt + 1, cnt + 2); add_edge(cnt + 1, cnt + 3); if(cnt / 4 % 3 != 2) add_edge(cnt + 3, cnt + 6); if(cnt < 24) add_edge(cnt + 1, cnt + 12); cnt += 4; } } return bfs(); } void add(int tt, int now) { int m[3][3], j; char temp[10]; char t[10]; sprintf(temp, "%09d", tt); for(int i = 0; i < 3; ++i) { for(j = 0; j < 3; ++j) m[i][j] = temp[i * 3 + j] - '0'; } for(int i = 0; i < 3; ++i) { for( j = 0; j < 3; ++j) { if(s[m[i][j]/3][m[i][j]%3][4] == '1') break; } if(j < 3) continue; memcpy(t, temp, 10); char ch; ch = t[i * 3], t[i * 3] = t[i * 3 + 1], t[i * 3 + 1] = t[i * 3 + 2], t[i * 3 + 2] = ch; sscanf(t, "%d", &tt); if(mmap.find(tt) == mmap.end()) { mmap[tt] = now; que.push(tt); } memcpy(t, temp, 10); //if(t== "180342675") // cout << "ans:" << check <<"t:" << t << endl; ch = t[i * 3 + 2], t[i * 3 + 2] = t[i * 3 + 1],t[i * 3 + 1] = t[i * 3], t[i * 3] = ch; sscanf(t, "%d", &tt); if(mmap.find(tt) == mmap.end()) { mmap[tt] = now; que.push(tt); } //if(t == "380264175") // cout << "ans:" << check <<"t:" << t << endl; } for(int i = 0; i < 3; ++i) { for(j = 0; j < 3; ++j) { if(s[m[j][i]/3][m[j][i]%3][4] == '1') break; } if(j < 3) continue; memcpy(t, temp, 10); char ch; ch = t[i], t[i] = t[i + 3], t[i + 3] = t[i + 6], t[i + 6] =ch; sscanf(t, "%d", &tt); if(mmap.find(tt) == mmap.end()) { mmap[tt] = now; que.push(tt); } memcpy(t, temp, 10); //if(t == "380642175") // cout << "ans:" << check <<"t:" << t << endl; ch = t[i + 6], t[i + 6] = t[i + 3], t[i + 3] =t[i], t[i] = ch; sscanf(t, "%d", &tt); if(mmap.find(tt) == mmap.end()) { mmap[tt] = now; que.push(tt); } // if(t == "018342675") // cout << "ans:" << check <<"t:" << t << endl; // if(t == "385260124") // cout << "ans:" << check <<"t:" << t << endl; } } int main() { int T; int cas = 0; for(cin >> T; T--;) { for(int i = 0; i < 3; ++i) { for(int j = 0; j < 3; ++j) { cin >> s[i][j]; } } int ans = 0; while(!que.empty())que.pop(); mmap.clear(); que.push(12345678); mmap[12345678] = 0; while(1) { int temp = que.front(); if(ok(temp)) { ans = mmap[temp]; break; } else add(temp, mmap[temp] + 1); que.pop(); } cout <<"Case #" << ++cas << ": " << ans << endl; } return 0; }