HDU 3278 Puzzle (蛋疼。。。。）

「爱情、让人受尽委屈。」 2022-03-29 05:50 202阅读 0赞

# 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: ![C217-1008.png][] 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<iostream>
    #include<cstdio>
    #include<cstring>
    #include<queue>
    
    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<int> 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;
    }

[C217-1008.png]: http://acm.hdu.edu.cn/data/images/C217-1008.png