Puzzle
Time Limit : 6000/3000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 15 Accepted Submission(s) : 8
Problem Description
One day, Resty gets a very interesting puzzle. Eve said that she will make a cake for Resty if he solved this puzzle, so Resty asks you to help him to solve the puzzle as soon as possible. As the figure, the puzzle is a rectangle divided into 4 * 6 = 24 squares. Each cell has a color of white / black/ grey. There are exactly 8 cells of each color. Our purpose is to make the middle 8 cells(which are not on the edge) have the same color by minimal steps. Each step, you could choose a row or a column to shift it for 1 bit. As following: 
Now, given the puzzle, you should help Resty find the minimal steps he must use to solve it.
Input
The first line is a number T, the number of test case. Each case contains 4 lines, each line contains a 6-length string, describe a puzzle. B for black color, W for white and G for grey.
Output
For each test, output on line in the Format “Case ID: ANS”, ANS should be the minimal number of steps to solve the puzzle.
Sample Input
3 GWGGWW BBBBBW GBBBGW WGGGWW GWGGWW BWBBBB GBBBGW WGGGWW WWWWWW BGGGGB WGGGGW BBBBBB
Sample Output
Case 1: 2
Case 2: 3
Case 3: 0
Author
Resty
Source
HDOJ Monthly Contest – 2010.01.02
题意很简单， 给一个4X6的矩形，其中又white ，blank ， grey 三种颜色各有8个格子 ，给定一个初始状态，求用最少的操作次数将图形变化为中间的8个格子颜色相同。
分析：一开始想到了IDA* ， 但是这题IDA* 是不行的， 原因我也不知道是为什么。 因为用三种颜色，在状态压缩的时候3^24显然会超内存，但是2^24不会超，这里用了一个很巧妙的预处理：从最终的状态开始考虑，即中间的8个格子都是一种颜色，这时旁边的两种颜色都可以看作一种颜色，因为它们对中间的颜色来说都是无关的，因此就可以将状态压缩到2^24，2kw。 预处理从最终的状态能到达的状态，并记录下step ， 因为有2Kw个状态，直接用int存step会超内存， 这里用char来代替int数组使用。。 最后1500ms水过。。
#include#include #include #include using namespace std;const int maxn=17000000;struct node{ int maze[4][6]; int Zip(){ int res=0; for(int i=0;i<4;i++) for(int j=0;j<6;j++){ res<<=1; res+=maze[i][j]; } return res; } void ReZip(int res){ for(int i=3;i>=0;i--) for(int j=5;j>=0;j--){ maze[i][j]=res&1; res>>=1; } }}s,t;void L_move(int si){ int i,j; for(i=0;i<4;i++){ if(si!=i){ for(j=0;j<6;j++) t.maze[i][j]=s.maze[i][j]; }else{ for(j=0;j<5;j++) t.maze[i][j]=s.maze[i][j+1]; t.maze[i][5]=s.maze[i][0]; } }}void R_move(int si){ int i,j; for(i=0;i<4;i++){ if(si!=i){ for(j=0;j<6;j++) t.maze[i][j]=s.maze[i][j]; }else{ for(j=5;j>0;j--) t.maze[i][j]=s.maze[i][j-1]; t.maze[i][0]=s.maze[i][5]; } }}void U_move(int sj){ int i,j; for(j=0;j<6;j++){ if(sj!=j){ for(i=0;i<4;i++) t.maze[i][j]=s.maze[i][j]; }else{ for(i=0;i<3;i++) t.maze[i][j]=s.maze[i+1][j]; t.maze[3][j]=s.maze[0][j]; } }}void D_move(int sj){ int i,j; for(j=0;j<6;j++){ if(sj!=j){ for(i=0;i<4;i++) t.maze[i][j]=s.maze[i][j]; }else{ for(i=3;i>0;i--) t.maze[i][j]=s.maze[i-1][j]; t.maze[0][j]=s.maze[3][j]; } }}char step[maxn]; //用int会超内存！！！！！！！！！！void BFS(){ memset(s.maze,0,sizeof(s.maze)); memset(t.maze,0,sizeof(t.maze)); for(int i=1;i<=2;i++) for(int j=1;j<=4;j++){ s.maze[i][j]=1; t.maze[i][j]=1; } int szip,nzip=s.Zip(); memset(step,-1,sizeof(step)); queue q; while(!q.empty()) q.pop(); q.push(nzip); step[nzip]=0; while(!q.empty()){ nzip=q.front(); q.pop(); s.ReZip(nzip); for(int i=0;i<4;i++){ R_move(i); szip=t.Zip(); if(step[szip]==-1){ step[szip]=step[nzip]+1; q.push(szip); } L_move(i); szip=t.Zip(); if(step[szip]==-1){ step[szip]=step[nzip]+1; q.push(szip); } } for(int i=0;i<6;i++){ U_move(i); szip=t.Zip(); if(step[szip]==-1){ step[szip]=step[nzip]+1; q.push(szip); } D_move(i); szip=t.Zip(); if(step[szip]==-1){ step[szip]=step[nzip]+1; q.push(szip); } } }}void Solve(int x){ for(int i=0;i<4;i++) for(int j=0;j<6;j++) if(s.maze[i][j]==x) t.maze[i][j]=1; else t.maze[i][j]=0;}int main(){ //freopen("input.txt","r",stdin); int T,res; BFS(); char map[6]; scanf("%d",&T); int cases=0; while(T--){ int i,j; for(i=0;i<4;i++){ scanf("%s",map); for(j=0;j<6;j++){ if(map[j]=='W') s.maze[i][j]=0; else if(map[j]=='B') s.maze[i][j]=1; else s.maze[i][j]=2; } } res=maxn; for(i=0;i<3;i++){ Solve(i); int nzip=t.Zip(); if(res>step[nzip]) res=step[nzip]; } printf("Case %d: %d\n",++cases,res); } return 0;}
