题目链接：点我
第一次不太清楚怎么判重，现在懂了，等下次再做
/*
*HDU 4531
*BFS
*注意判重
*/ #include <stdio.h>
#include <string.h>
#include <algorithm>
#include <map>
#include <set>
#include <string>
#include <queue>
#include <iostream>
using namespace std; char str[][][];
char g[][][]; map<int,int>mp;
queue<int>q;
bool move[];//是否可以移动，0~5对应1~3行，1~3列 //并查集判断连通
int F[];
int find(int x)
{
if(F[x]==-)return x;
return F[x]=find(F[x]);
}
void bing(int x,int y)
{
int t1=find(x);
int t2=find(y);
if(t1!=t2)F[t1]=t2;
}
//并查集判断是不是连通
bool judge(int state)//判断状态state是不是连通
{
char temp[];
int t[];
sprintf(temp,"%09d",state);
for(int i=;i<;i++)t[i]=temp[i]-'';
for(int i=;i<;i++)
for(int j=;j<;j++)
{
int p=t[*i+j];
int x=p/;
int y=p%;
strcpy(g[i][j],str[x][y]);
}
memset(F,-,sizeof(F));
for(int i=;i<;i++)
for(int j=;j<;j++)
{
if(g[i][j][]==g[i][j][])bing(*i+*j,*i+*j+);
if(g[i][j][]==g[i][j][])bing(*i+*j,*i+*j+);
if(g[i][j][]==g[i][j][])bing(*i+*j+,*i+*j+);
if(g[i][j][]==g[i][j][])bing(*i+*j+,*i+*j+);
}
for(int i=;i<;i++)
{
if(g[i][][]==g[i][][])bing(*i+,*i++);
if(g[i][][]==g[i][][])bing(*i++,*i++);
}
for(int j=;j<;j++)
{
if(g[][j][]==g[][j][])bing(*j+,+*j+);
if(g[][j][]==g[][j][])bing(+*j+,+*j+);
}
int R=-,G=-,B=-,O=-;
for(int i=;i<;i++)
for(int j=;j<;j++)
for(int k=;k<;k++)
{
int t1=find(*i+*j+k);
if(g[i][j][k]=='R')
{
if(R==-)R=t1;
else if(t1!=R)return false;
}
else if(g[i][j][k]=='G')
{
if(G==-)G=t1;
else if(t1!=G)return false;
}
else if(g[i][j][k]=='B')
{
if(B==-)B=t1;
else if(t1!=B)return false;
}
else
{
if(O==-)O=t1;
else if(t1!=O)return false;
}
}
return true;
}
int bfs()
{
mp.clear();
while(!q.empty())q.pop();
int tmp,now;
char ss1[],ss2[];
tmp=; //初始是012345678
mp[tmp]=;
q.push(tmp);
while(!q.empty())
{
tmp=q.front();
q.pop();
if(judge(tmp))return mp[tmp];
sprintf(ss1,"%09d",tmp); for(int i=;i<;i++)
for(int j=;j<;j++)
{
int t=ss1[*i+j]-'';
strcpy(g[i][j],str[t/][t%]);
}
//第一行的左右移动
if(move[])
{
strcpy(ss2,ss1);
ss2[]=ss1[];
ss2[]=ss1[];
ss2[]=ss1[];
now=;
for(int i=;i<;i++)
{
now*=;
now+=ss2[i]-'';
}
if(mp.find(now)==mp.end())
{
mp[now]=mp[tmp]+;
q.push(now);
} ss2[]=ss1[];
ss2[]=ss1[];
ss2[]=ss1[];
now=;
for(int i=;i<;i++)
{
now*=;
now+=ss2[i]-'';
}
if(mp.find(now)==mp.end())
{
mp[now]=mp[tmp]+;
q.push(now);
} } //第二行的左右移动
if(move[])
{
strcpy(ss2,ss1);
ss2[]=ss1[];
ss2[]=ss1[];
ss2[]=ss1[];
now=;
for(int i=;i<;i++)
{
now*=;
now+=ss2[i]-'';
}
if(mp.find(now)==mp.end())
{
mp[now]=mp[tmp]+;
q.push(now);
}
ss2[]=ss1[];
ss2[]=ss1[];
ss2[]=ss1[];
now=;
for(int i=;i<;i++)
{
now*=;
now+=ss2[i]-'';
}
if(mp.find(now)==mp.end())
{
mp[now]=mp[tmp]+;
q.push(now);
}
} //第三行的左右移动
if(move[])
{
strcpy(ss2,ss1);
ss2[]=ss1[];
ss2[]=ss1[];
ss2[]=ss1[];
now=;
for(int i=;i<;i++)
{
now*=;
now+=ss2[i]-'';
}
if(mp.find(now)==mp.end())
{
mp[now]=mp[tmp]+;
q.push(now);
} ss2[]=ss1[];
ss2[]=ss1[];
ss2[]=ss1[];
now=;
for(int i=;i<;i++)
{
now*=;
now+=ss2[i]-'';
}
if(mp.find(now)==mp.end())
{
mp[now]=mp[tmp]+;
q.push(now);
} } //第一列的左右移动
if(move[])
{
strcpy(ss2,ss1);
ss2[]=ss1[];
ss2[]=ss1[];
ss2[]=ss1[];
now=;
for(int i=;i<;i++)
{
now*=;
now+=ss2[i]-'';
}
if(mp.find(now)==mp.end())
{
mp[now]=mp[tmp]+;
q.push(now);
} ss2[]=ss1[];
ss2[]=ss1[];
ss2[]=ss1[];
now=;
for(int i=;i<;i++)
{
now*=;
now+=ss2[i]-'';
}
if(mp.find(now)==mp.end())
{
mp[now]=mp[tmp]+;
q.push(now);
} } //第二列的左右移动
if(move[])
{
strcpy(ss2,ss1);
ss2[]=ss1[];
ss2[]=ss1[];
ss2[]=ss1[];
now=;
for(int i=;i<;i++)
{
now*=;
now+=ss2[i]-'';
}
if(mp.find(now)==mp.end())
{
mp[now]=mp[tmp]+;
q.push(now);
} ss2[]=ss1[];
ss2[]=ss1[];
ss2[]=ss1[];
now=;
for(int i=;i<;i++)
{
now*=;
now+=ss2[i]-'';
}
if(mp.find(now)==mp.end())
{
mp[now]=mp[tmp]+;
q.push(now);
} } //第三列的左右移动
if(move[])
{
strcpy(ss2,ss1);
ss2[]=ss1[];
ss2[]=ss1[];
ss2[]=ss1[];
now=;
for(int i=;i<;i++)
{
now*=;
now+=ss2[i]-'';
}
if(mp.find(now)==mp.end())
{
mp[now]=mp[tmp]+;
q.push(now);
} ss2[]=ss1[];
ss2[]=ss1[];
ss2[]=ss1[];
now=;
for(int i=;i<;i++)
{
now*=;
now+=ss2[i]-'';
}
if(mp.find(now)==mp.end())
{
mp[now]=mp[tmp]+;
q.push(now);
}
} }
return -;
} int main()
{
int T;
scanf("%d",&T);
int iCase=;
while(T--)
{
iCase++;
printf("Case #%d: ",iCase);
for(int i=;i<;i++)move[i]=true;
for(int i=;i<;i++)
for(int j=;j<;j++)
{
scanf("%s",&str[i][j]);
if(str[i][j][]=='')//所在的列和行不能移动
{
move[i]=false;
move[+j]=false;
}
}
printf("%d\n",bfs());
}
return ;
}