比较烦人的一道题目，看着题目都觉得很吓人，不过模拟题终究是模拟题， 耐心点还是可以过的。
题意： 给出了一个3*3的方块，每个方块有上下左右四个颜色， 然后每次可以在一行上 左/右循环移一格， 或一列上 上/下循环移一格。 求最少操作次数使的3*3中相同颜色的块形成一个连通块。
因为只有9个方块，所以最多的状态数为9! , 10^6次方的复杂度还是可以接受的。
然后就是一系列比较复杂的变换，搜索。 耐心点还是没有问题的。
写了几个小时 ，1 A
吉哥系列故事——乾坤大挪移
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 240 Accepted Submission(s): 72
Problem Description
只有进入本次马拉松复赛，你才有机会知道一个秘密：吉哥的真名叫基哥，江湖人称“叽叽哥”。
叽叽哥除了编程，还一直有个武侠梦，他最喜欢的人物是金庸小说《倚天屠龙记》中的张无忌，不仅有美人环绕，而且有一身的好武功，尤其是那神秘的乾坤大挪移，让他梦寐以求：
“乾坤大挪移乃在颠倒一刚一柔、一阴一阳的乾坤二气，随意而行，不用心而无不心用，所谓至我逍遥游，以纯阳之身，和纯阴之体，合练双修，不动身，只用意，意动身守......”
但是，梦毕竟只是梦，平时在编程的空闲时间，叽叽哥也最多只能上网玩一下名为“乾坤大挪移”的游戏聊以自慰而已。
这个“乾坤大挪移”游戏是在3*3的方格中进行。
游戏的目标是通过移动，让相同颜色的块形成一个连通块(相邻是指两个块有边相邻,角相邻不算)。
移动规则如下:选择一行(列),向左右(上下)移动一格,方格从一边划出,则从对应的另外一边划入,像履带一样。
如选择第一行向右边移动,最右边的那格会移动到最左边。
游戏中还有一些方格被固定住,这些方格没办法移动(如下图的第三行第二列)。
下图是游戏的一个演示(即Case 1):
假设现在告诉你初始状态,请问你最少需要几步才能达到目标？
叽叽哥除了编程，还一直有个武侠梦，他最喜欢的人物是金庸小说《倚天屠龙记》中的张无忌，不仅有美人环绕，而且有一身的好武功，尤其是那神秘的乾坤大挪移，让他梦寐以求：
“乾坤大挪移乃在颠倒一刚一柔、一阴一阳的乾坤二气，随意而行，不用心而无不心用，所谓至我逍遥游，以纯阳之身，和纯阴之体，合练双修，不动身，只用意，意动身守......”
但是，梦毕竟只是梦，平时在编程的空闲时间，叽叽哥也最多只能上网玩一下名为“乾坤大挪移”的游戏聊以自慰而已。
这个“乾坤大挪移”游戏是在3*3的方格中进行。
游戏的目标是通过移动，让相同颜色的块形成一个连通块(相邻是指两个块有边相邻,角相邻不算)。
移动规则如下:选择一行(列),向左右(上下)移动一格,方格从一边划出,则从对应的另外一边划入,像履带一样。
如选择第一行向右边移动,最右边的那格会移动到最左边。
游戏中还有一些方格被固定住,这些方格没办法移动(如下图的第三行第二列)。
下图是游戏的一个演示(即Case 1):
假设现在告诉你初始状态,请问你最少需要几步才能达到目标？
Input
第一行一个整数T代表接下去有T组数据;
每组数据由3*3的模块组成，每个模块表示的小正方形是由上下左右四个小三角形组成;
每个模块有5个字符,前四个字符分别表示组成正方形的上下左右四个小三角形的颜色,第五个字符表示该格子能否移动(0表示能移动,1表示不能移动).
[Technical Specification]
0<T<=100
代表颜色的字符一定是RGBO的其中一个
代表能否移动移动的字符一定是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
Sample Output
Case #1: 5 Case #2: 2
Source
Recommend
liuyiding
#include <stdio.h> #include <string.h> #include <queue> #include <algorithm> #include <iostream> using namespace std; #define INF 0x3fffffff struct node { char up,dn,ri,lt; int id; }g[3][3]; struct ss { node k[3][3]; }; int mi; int sign[2][3]; // 表示那些操作不能进行 bool mark[10001000]; int mark1[3][3][4]; int save[11]={1,1,2,6,24,120,720,5040,40320,362880,3628800}; queue<ss> que[2]; int cantuo(node s[3][3]) { int ct[10]; int cnt=1; for(int i=0;i<3;i++) for(int j=0;j<3;j++) ct[cnt++]=s[i][j].id; int sum=0; for(int i=1;i<=9;i++) { cnt=0; for(int j=i+1;j<=9;j++) if(ct[i]>ct[j]) cnt++; sum+=save[9-i]*cnt; } return sum; } int change(char c) { if(c=='R') return 0; if(c=='G') return 1; if(c=='B') return 2; return 3; } int dfs(int x,int y,int flag,char key,node s[3][3]) { int cnt=0; if(flag==0||flag==1) { if(s[x][y].lt == key&&mark1[x][y][3]==0) { mark1[x][y][3]=1; cnt+=dfs(x,y,3,key,s); } if(s[x][y].ri == key&&mark1[x][y][2]==0) { mark1[x][y][2]=1; cnt+=dfs(x,y,2,key,s); } } else { if(s[x][y].up==key&&mark1[x][y][0]==0) { mark1[x][y][0]=1; cnt+=dfs(x,y,0,key,s); } if(s[x][y].dn==key&&mark1[x][y][1]==0) { mark1[x][y][1]=1; cnt+=dfs(x,y,1,key,s); } } if(flag==0&&x!=0&&s[x-1][y].dn==key && mark1[x-1][y][1]==0) { mark1[x-1][y][1]=1; cnt+=dfs(x-1,y,1,key,s); } if(flag==1&&x!=2&&s[x+1][y].up==key && mark1[x+1][y][0]==0) { mark1[x+1][y][0]=1; cnt+=dfs(x+1,y,0,key,s); } if(flag==2&&y!=2&&s[x][y+1].lt==key && mark1[x][y+1][3]==0) { mark1[x][y+1][3]=1; cnt+=dfs(x,y+1,3,key,s); } if(flag==3&&y!=0&&s[x][y-1].ri==key&&mark1[x][y-1][2]==0) { mark1[x][y-1][2]=1; cnt+=dfs(x,y-1,2,key,s); } return cnt+1; } int check(node s[3][3]) // 比较关键的一步，判断是否联通. { memset(mark1,0,sizeof(mark1)); int tmark[4]; memset(tmark,0,sizeof(tmark)); // R=0,G=1,B=2,O=3; int sum=0; // up 0, dn 1, ri 2,lt 3 for(int i=0;i<3;i++) for(int j=0;j<3;j++) { if( tmark[change(s[i][j].up)]==0 ) { tmark[change(s[i][j].up)]=1; mark1[i][j][0]=1; sum+=dfs(i,j,0,s[i][j].up,s); } if (tmark[change(s[i][j].dn)]==0 ) { tmark[change(s[i][j].dn)]=1; mark1[i][j][1]=1; sum+=dfs(i,j,1,s[i][j].dn,s); } if (tmark[change(s[i][j].ri)]==0) { tmark[change(s[i][j].ri)]=1; mark1[i][j][2]=1; sum+=dfs(i,j,2,s[i][j].ri,s); } if (tmark[change(s[i][j].lt)]==0) { tmark[change(s[i][j].lt)]=1; mark1[i][j][3]=1; sum+=dfs(i,j,3,s[i][j].lt,s); } } if(sum==9*4) return 1; else return 0; } void print(node s[3][3]) { printf("##############\n"); for(int i=0;i<3;i++) { for(int j=0;j<3;j++) { printf("%d ",s[i][j].id); } printf("\n"); } printf("##################\n"); } int bfs() { memset(mark,0,sizeof(mark)); int a=0,b=1; while(que[0].size()!=0) que[0].pop(); while(que[1].size()!=0) que[1].pop(); //清空 ss ts; for(int i=0;i<3;i++) for(int j=0;j<3;j++) ts.k[i][j]=g[i][j]; que[0].push(ts); int tmp=cantuo(g); mark[tmp]=1; int cnt=-1; ss cur,nwnode; node tnode; while(que[a].size()!=0) { cnt++; swap(a,b); while(que[b].size()!=0) { cur=que[b].front(); que[b].pop(); if(check(cur.k)==1) { return cnt; } //nwnode=cur; for(int i=0;i<3;i++) { if(sign[0][i]==1) continue; //print(cur.k); tnode=cur.k[i][0]; cur.k[i][0]=cur.k[i][1]; cur.k[i][1]=cur.k[i][2]; cur.k[i][2]=tnode; //print(cur.k); int id=cantuo(cur.k); if(mark[id]==0) { mark[id]=1; que[a].push(cur); } tnode=cur.k[i][0]; cur.k[i][0]=cur.k[i][2]; cur.k[i][2]=cur.k[i][1]; cur.k[i][1]=tnode; // 恢复了 //print(cur.k); ////////////////////////////// tnode=cur.k[i][0]; cur.k[i][0]=cur.k[i][2]; cur.k[i][2]=cur.k[i][1]; cur.k[i][1]=tnode; //print(cur.k); id=cantuo(cur.k); if(mark[id]==0) { mark[id]=1; que[a].push(cur); } tnode=cur.k[i][0]; cur.k[i][0]=cur.k[i][1]; cur.k[i][1]=cur.k[i][2]; cur.k[i][2]=tnode; //print(cur.k); } for(int i=0;i<3;i++) { if(sign[1][i]==1) continue; tnode=cur.k[0][i]; cur.k[0][i]=cur.k[1][i]; cur.k[1][i]=cur.k[2][i]; cur.k[2][i]=tnode; int id=cantuo(cur.k); if(mark[id]==0) { mark[id]=1; que[a].push(cur); } tnode=cur.k[0][i]; cur.k[0][i]=cur.k[2][i]; cur.k[2][i]=cur.k[1][i]; cur.k[1][i]=tnode; ///////////////// tnode=cur.k[0][i]; cur.k[0][i]=cur.k[2][i]; cur.k[2][i]=cur.k[1][i]; cur.k[1][i]=tnode; id=cantuo(cur.k); if(mark[id]==0) { mark[id]=1; que[a].push(cur); } tnode=cur.k[0][i]; cur.k[0][i]=cur.k[1][i]; cur.k[1][i]=cur.k[2][i]; cur.k[2][i]=tnode; } } } } int main() { int tt=1; int t; scanf("%d",&t); while(t--) { memset(sign,0,sizeof(sign)); char str[10]; for(int i=0;i<3;i++) for(int j=0;j<3;j++) { scanf("%s",str); g[i][j].up=str[0]; g[i][j].dn=str[1]; g[i][j].lt=str[2]; g[i][j].ri=str[3]; g[i][j].id=i*3+j; if(str[4]=='1') { sign[0][i]=1; sign[1][j]=1; // 涉及到这个格子的操作都不能进行. } } printf("Case #%d: %d\n",tt++,bfs()); } return 0; }