本文共 1692 字，大约阅读时间需要 5 分钟。
这道搜索题挺恶心的。。。比赛时没有写出来。
首先要解决的问题是怎样判断符合条件的状态，即所有一样的颜色是连在一起的。我是采用最简单也最搓的方法，按上下左右顺序给每一个小三角形标号1～36，然后建立一张邻接矩阵图，然后bfs判断。
然后就是主要的暴力枚举部分，每次有12种状态转移的选择，开始时用dfs，但爆栈了。然后改成bfs，又各种TLE。然后就是不断地优化优化。
判重的状态可以用一个整数来表示。
矩阵初始标号为：
1 2 3
4 5 6
7 8 9
那么它的状态就是123456789. 采用哈希判断方法。
代码：
#include#include #include #include using namespace std;typedef int int64;const int HashSize = 1000003; // 哈希值尺寸，视情况而定const int MaxState = 400000; // 共需要存多少个const int MAXQUE = 500000;int g[40][40];int mat[3][3];char str[12][6];bool vis[40], alpha[150];bool isCol[3], isRow[3];int ans;vector G[40];template 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 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
转载地址：http://mszni.baihongyu.com/