题目链接http://acm.hdu.edu.cn/showproblem.php?pid=4531
吉哥系列故事——乾坤大挪移
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 555 Accepted Submission(s): 178
Problem Description
只有进入本次马拉松复赛，你才有机会知道一个秘密：吉哥的真名叫基哥，江湖人称“叽叽哥”。
叽叽哥除了编程，还一直有个武侠梦，他最喜欢的人物是金庸小说《倚天屠龙记》中的张无忌，不仅有美人环绕，而且有一身的好武功，尤其是那神秘的乾坤大挪移，让他梦寐以求：
“乾坤大挪移乃在颠倒一刚一柔、一阴一阳的乾坤二气，随意而行，不用心而无不心用，所谓至我逍遥游，以纯阳之身，和纯阴之体，合练双修，不动身，只用意，意动身守......”
但是，梦毕竟只是梦，平时在编程的空闲时间，叽叽哥也最多只能上网玩一下名为“乾坤大挪移”的游戏聊以自慰而已。
这个“乾坤大挪移”游戏是在3*3的方格中进行。
游戏的目标是通过移动，让相同颜色的块形成一个连通块(相邻是指两个块有边相邻,角相邻不算)。
移动规则如下:选择一行(列),向左右(上下)移动一格,方格从一边划出,则从对应的另外一边划入,像履带一样。
如选择第一行向右边移动,最右边的那格会移动到最左边。
游戏中还有一些方格被固定住,这些方格没办法移动(如下图的第三行第二列)。
下图是游戏的一个演示(即Case 1):
假设现在告诉你初始状态,请问你最少需要几步才能达到目标？
Input
第一行一个整数T代表接下去有T组数据;
每组数据由3*3的模块组成，每个模块表示的小正方形是由上下左右四个小三角形组成;
每个模块有5个字符,前四个字符分别表示组成正方形的上下左右四个小三角形的颜色,第五个字符表示该格子能否移动(0表示能移动,1表示不能移动).
每组数据由3*3的模块组成，每个模块表示的小正方形是由上下左右四个小三角形组成;
每个模块有5个字符,前四个字符分别表示组成正方形的上下左右四个小三角形的颜色,第五个字符表示该格子能否移动(0表示能移动,1表示不能移动).
[Technical Specification]
0<T<=100
代表颜色的字符一定是RGBO的其中一个
代表能否移动移动的字符一定是0或者1
Output
首先输出case数,接着输出最小的移动步数使得游戏达到目标状态(见sample);
数据保证有解。
数据保证有解。
Sample Input
2
GGGG0 GGGG0 GGGG0
OGOO0 GGGG0 OGOO0
OOOO0 OGGG1 OOOO0
RRRR0 OOOO0 OOOO0
OOOO0 OOOO0 OOOO0
OOOO0 OOOO0 RRRR0
GGGG0 GGGG0 GGGG0
OGOO0 GGGG0 OGOO0
OOOO0 OGGG1 OOOO0
RRRR0 OOOO0 OOOO0
OOOO0 OOOO0 OOOO0
OOOO0 OOOO0 RRRR0
Sample Output
Case #1: 5
Case #2: 2
Case #2: 2
Source
看到题目，确实感觉有点麻烦，很考验代码能力，代码能力差的话可能要写很长的代码，容易犯错。
首先类似于八数码问题的棋盘规格，我们考虑使用康拓展开作为状态压缩标记走过的棋盘样式，最多9！种状态。
节点保存棋盘压缩值，步数，棋盘样式。为了方便将每个方格内的四个三角分别对应0,1,2,3，那么a[i][j][k]就可以方便的表示i行j列第k个三角。
每次检查当前头部节点对应的棋盘是否达到了目标状态。这个听别人用的并查集，我没有用，我是dfs染色统计每个颜色联通快的个数，如果每个颜色的个数都<=1,说明当前就是一个合法的状态。关键就是dfs时的方向问题困扰了我，我们常见的方形棋盘一般就是4/8个直观的方形，这个却是三角，其实也不是很难，我们只要dfs三角形的三条边不就好了吗，一共四种三角分类讨论一下也就好了。最后就是有12种移动方式，简单的交换一下就好了，注意提前判断一下是否有不可移动的格子。
#include<bits/stdc++.h>
using namespace std;
bool vis[];
int f[]={,,,,,,,,,};
struct node
{
int cal,bs;
char e[];
};
void change1(node &t,int type)
{
switch(type)
{
case :swap(t.e[],t.e[]);swap(t.e[],t.e[]);break;
case :swap(t.e[],t.e[]);swap(t.e[],t.e[]);break;
case :swap(t.e[],t.e[]);swap(t.e[],t.e[]);break;
case :swap(t.e[],t.e[]);swap(t.e[],t.e[]);break;
case :swap(t.e[],t.e[]);swap(t.e[],t.e[]);break;
case :swap(t.e[],t.e[]);swap(t.e[],t.e[]);break;
case :swap(t.e[],t.e[]);swap(t.e[],t.e[]);break;
case :swap(t.e[],t.e[]);swap(t.e[],t.e[]);break;
case :swap(t.e[],t.e[]);swap(t.e[],t.e[]);break;
case :swap(t.e[],t.e[]);swap(t.e[],t.e[]);break;
case :swap(t.e[],t.e[]);swap(t.e[],t.e[]);break;
case :swap(t.e[],t.e[]);swap(t.e[],t.e[]);break;
} }
int cal(node A)
{
int s=,i,j;
for(i=;i<;++i)
{
int c=;
for(j=i+;j<;++j)
if(A.e[j]<A.e[i]) c++;
s+=c*f[-i];
}
return s;
}
struct nic
{
char color[];
}a[][],b[][];
bool mov[][];
bool book[][][];
void dfs(int x,int y,int is,char clo)
{
if(x<||y<||x>||y>||is<||is>||b[x][y].color[is]!=clo||book[x][y][is]) return;
b[x][y].color[is]='X';
book[x][y][is]=;
if(is==){
dfs(x-,y,,clo);
dfs(x,y,,clo);
dfs(x,y,,clo);
}
else if(is==){
dfs(x,y+,,clo);
dfs(x,y,,clo);
dfs(x,y,,clo);
}
else if(is==){
dfs(x+,y,,clo);
dfs(x,y,,clo);
dfs(x,y,,clo);
}
else{
dfs(x,y-,,clo);
dfs(x,y,,clo);
dfs(x,y,,clo);
}
}
bool ok(node A)
{
int G=,B=,R=,O=,i,j,k,p=;
for(i=;i<=;++i)
for(j=;j<=;++j,p++){
int di=((int)(A.e[p]-''))/+,dj=((int)(A.e[p]-''))%+;
for(k=;k<;++k)
b[i][j].color[k]=a[di][dj].color[k];
}
for(i=;i<=;++i)
for(j=;j<=;++j)
for(k=;k<;++k)
{
if(b[i][j].color[k]=='G')
{G++;}
else if(b[i][j].color[k]=='B')
B++;
else if(b[i][j].color[k]=='R')
R++;
else if(b[i][j].color[k]=='O')
O++;
else continue;
memset(book,,sizeof(book));
dfs(i,j,k,b[i][j].color[k]);
}
return (G<=&&B<=&&R<=&&O<=);
}
int bfs()
{
queue<node>Q;
memset(vis,,sizeof(vis));
node t1,t2;
t1.cal=;
t1.bs=;
strcpy(t1.e,"");
ok(t1);
Q.push(t1);
while(!Q.empty()){
t1=Q.front();Q.pop();
if(ok(t1)) {return t1.bs;}
if(vis[t1.cal]) continue;
vis[t1.cal]=;
for(int i=;i<=;++i)
{
if(i<=&&mov[][(i+)/]) continue;
if(i>&&mov[][(i+)/-]) continue;
node tmp=t1;
tmp.bs++;
change1(tmp,i);
tmp.cal=cal(tmp);
if(!vis[tmp.cal]) Q.push(tmp);
}
}
return -;
}
int main()
{
int T,N,M,i,j,cas=,n,m,k;
int index[]={,,,};
cin>>T;
while(T--){
memset(mov,,sizeof(mov));
memset(a,,sizeof(a));
for(i=;i<=;++i)
for(j=;j<=;++j)
{
for(k=;k<;++k)
cin>>a[i][j].color[index[k]];
scanf("%d",&m);
if(m==) mov[][i]=mov[][j]=;
}
printf("Case #%d: %d\n",++cas,bfs());
}
return ;
}