题目链接:
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;
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<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\n",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);
}
}
}
分享到:
相关推荐
算法设计与分析实验六:使用动态规划算法解决存钱问题(java实现、hdu1114)(csdn)————程序
hdu ACM 高级程序设计习题集——全文 里面有程序的详细解释
你活的不容易,我活的不容易,他活的也不容易。不过,如果你看了下面的故事,就会知道,有位老汉比你还不容易。
本压缩包内包含杭电ACM集训的课件PPT,较为详细的介绍了动态规划,计算几何,贪心算法, 搜索,二分图及其应用,母函数及其应用,组合博弈入门,并查集,递推求解等常用算法
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
HDU1059的代码
杭电ACMhdu1163
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
ACM HDU题目分类,我自己总结的大概只有十来个吧
HDU最全ac代码
hdu 1166线段树代码
hdu动态规划算法集锦