首页 > ACM题库 > HDU-杭电 > HDU 4531-吉哥系列故事――乾坤大挪移-BFS-[解题报告]HOJ
2015
07-17

HDU 4531-吉哥系列故事――乾坤大挪移-BFS-[解题报告]HOJ

吉哥系列故事――乾坤大挪移

问题描述 :

  只有进入本次马拉松复赛,你才有机会知道一个秘密:吉哥的真名叫基哥,江湖人称“叽叽哥”。

  叽叽哥除了编程,还一直有个武侠梦,他最喜欢的人物是金庸小说《倚天屠龙记》中的张无忌,不仅有美人环绕,而且有一身的好武功,尤其是那神秘的乾坤大挪移,让他梦寐以求:
  
  “乾坤大挪移乃在颠倒一刚一柔、一阴一阳的乾坤二气,随意而行,不用心而无不心用,所谓至我逍遥游,以纯阳之身,和纯阴之体,合练双修,不动身,只用意,意动身守……”
  
  但是,梦毕竟只是梦,平时在编程的空闲时间,叽叽哥也最多只能上网玩一下名为“乾坤大挪移”的游戏聊以自慰而已。
  这个“乾坤大挪移”游戏是在3*3的方格中进行。
  游戏的目标是通过移动,让相同颜色的块形成一个连通块(相邻是指两个块有边相邻,角相邻不算)。
  移动规则如下:选择一行(列),向左右(上下)移动一格,方格从一边划出,则从对应的另外一边划入,像履带一样。
  如选择第一行向右边移动,最右边的那格会移动到最左边。
  游戏中还有一些方格被固定住,这些方格没办法移动(如下图的第三行第二列)。
  下图是游戏的一个演示(即Case 1):

小Q系列故事――大笨钟

  假设现在告诉你初始状态,请问你最少需要几步才能达到目标?

输入:

第一行一个整数T代表接下去有T组数据;
每组数据由3*3的模块组成,每个模块表示的小正方形是由上下左右四个小三角形组成;
每个模块有5个字符,前四个字符分别表示组成正方形的上下左右四个小三角形的颜色,第五个字符表示该格子能否移动(0表示能移动,1表示不能移动).

[Technical Specification]
0<T<=100
代表颜色的字符一定是RGBO的其中一个
代表能否移动移动的字符一定是0或者1

输出:

第一行一个整数T代表接下去有T组数据;
每组数据由3*3的模块组成,每个模块表示的小正方形是由上下左右四个小三角形组成;
每个模块有5个字符,前四个字符分别表示组成正方形的上下左右四个小三角形的颜色,第五个字符表示该格子能否移动(0表示能移动,1表示不能移动).

[Technical Specification]
0<T<=100
代表颜色的字符一定是RGBO的其中一个
代表能否移动移动的字符一定是0或者1

样例输入:

2
GGGG0 GGGG0 GGGG0
OGOO0 GGGG0 OGOO0
OOOO0 OGGG1 OOOO0
RRRR0 OOOO0 OOOO0
OOOO0 OOOO0 OOOO0
OOOO0 OOOO0 RRRR0

样例输出:

Case #1: 5
Case #2: 2

题目链接:

http://acm.hdu.edu.cn/showproblem.php?pid=4531

这道搜索题挺恶心的。。。比赛时没有写出来。

首先要解决的问题是怎样判断符合条件的状态,即所有一样的颜色是连在一起的。我是采用最简单也最搓的方法,按上下左右顺序给每一个小三角形标号1~36,然后建立一张邻接矩阵图,然后bfs判断。

然后就是主要的暴力枚举部分,每次有12种状态转移的选择,开始时用dfs,但爆栈了。然后改成bfs,又各种TLE。然后就是不断地优化优化。

判重的状态可以用一个整数来表示。

矩阵初始标号为:

1 2 3

4 5 6

7 8 9

那么它的状态就是123456789. 采用哈希判断方法。

代码:

#include<cstdio>
#include<cstring>
#include<vector>
#include<cctype>
using namespace std;

typedef int int64;

const int HashSize = 1000003; // 哈希值尺寸,视情况而定
const int MaxState = 400000;     // 共需要存多少个
const int MAXQUE = 500000;

int  g[40][40];
int  mat[3][3];
char str[12][6];
bool vis[40], alpha[150];
bool isCol[3], isRow[3];
int  ans;
vector<int>G[40];


template<typename Type>
class Hash{
public:
    void init(){
        rear=1;  
        memset(head, -1, sizeof(head));
        memset(state, -1, sizeof(state));
    }

    int insert(Type s){  
        int h = hash(s), u = head[h];
        while(u!=-1){
            if(state[u] == s) return u; //返回所在位置
            u = next[u];
        }
        state[rear] = s;
        next[rear] = head[h];
        head[h] = rear++;
        return rear-1;  // 返回新插入的位置
    }
    int find(Type s){
        int h = hash(s), u = head[h];
        while(u!=-1){
            if(state[u] == s) return u; //返回所在位置
            u = next[u];
        }
        return 0;
    }

private:
    int hash(Type x){
        int d = ((x&0x7fffffff)%HashSize);
        return d;
    }
private:
    int head[HashSize], next[MaxState], rear;
    Type state[MaxState];
};
Hash<int64>hash;


inline void init();

struct Node{
    int st;
    int cnt;
}Q[MAXQUE];


int que[100];
char s[40];
inline bool bfs(int st){
    int pos=35;
    while(st>0){
        int p = st%10;
        for(int k=3; k>=0; --k) s[pos--] = str[p][k];
        st /= 10;
    }
    memset(alpha, 0, sizeof(alpha));
    memset(vis, 0, sizeof(vis));

    for(int i=0; i<36; ++i)if(!vis[i+1]){
        if(alpha[s[i]]) return false;
        vis[i+1] = true;
        int front=0, rear=1;
        que[0] = i+1;
        while(front < rear){
            int u = que[front++];
            for(int j=0; j<G[u].size(); ++j){
                int v = G[u][j];
                if(!vis[v] && s[v-1]==s[u-1]){
                    vis[v] = true;
                    que[rear++] = v;
                }
            }
        }
        alpha[s[i]] = true;
    }
    return true;
}

char buf[15];
inline int rotateRow(int st, int row){
    sprintf(buf, "%d", st);
    char tmp = buf[row*3];
    buf[row*3] = buf[row*3+1];
    buf[row*3+1] = buf[row*3+2];
    buf[row*3+2] = tmp;
    sscanf(buf, "%d", &st);
    return st;
}
inline int rotateCol(int st, int col){
    sprintf(buf, "%d", st);
    char tmp = buf[col];
    buf[col]   = buf[3+col];
    buf[3+col] = buf[6+col];
    buf[6+col] = tmp;
    sscanf(buf, "%d", &st);
    return st;
}

inline void solve(){
    Q[0].st = 123456789;
    Q[0].cnt = 0;
    int front=0, rear=1;
    hash.insert(Q[0].st);
    while(front < rear){
        const Node& q = Q[front++];

	    if(bfs(q.st)){
            ans = q.cnt;
            return ;
        }

        int st;
        for(int i=0; i<3; ++i){
            if(!isRow[i]) {
                st = rotateRow(q.st, i);
                if(!hash.find(st)){
                    hash.insert(st);
                    Q[rear].st = st;
                    Q[rear++].cnt = q.cnt+1;
                }

                st = rotateRow(st, i);
                if(!hash.find(st)){
                    hash.insert(st);
                    Q[rear].st = st;
                    Q[rear++].cnt = q.cnt+1;
                }
            }
            if(!isCol[i]){
                st = rotateCol(q.st, i);
                if(!hash.find(st)){
                    hash.insert(st);
                    Q[rear].st = st;
                    Q[rear++].cnt = q.cnt+1;
                }

                st = rotateCol(st, i);
                if(!hash.find(st)){
                    hash.insert(st);
                    Q[rear].st = st;
                    Q[rear++].cnt = q.cnt+1;
                }
            }
        }
    }
}

int main(){
   
    int T, cas=1;
    init();
    scanf("%d", &T);

    while(T--){
         
        int idx=1;
        memset(isRow, 0, sizeof(isRow));
        memset(isCol, 0, sizeof(isCol));
        for(int i=0; i<3; ++i){
            for(int j=0; j<3; ++j){
                char& ch = str[idx][0];
                ch = getchar();
                while(!isalpha(ch)) ch=getchar();
                for(int k=1; k<5; ++k) str[idx][k] = getchar();
                if(str[idx][4] == '1') 
                    isRow[i]=isCol[j]=true;
                mat[i][j] = idx++;
            }
        }

        hash.init();
        ans = 100000000;
        solve();
        printf("Case #%d: %d\n",cas++, ans);

    }
    
    return 0;
}



// =============================
inline void init(){
memset(g, 0, sizeof(g));
	g[1][3]=1, g[1][4]=1, 
	g[5][7]=1, g[5][8]=1, 
	g[9][11]=1, g[9][12]=1, 
	g[13][2]=1, g[13][15]=1, g[13][16]=1, 
	g[17][6]=1, g[17][19]=1, g[17][20]=1, 
	g[21][10]=1, g[21][23]=1, g[21][24]=1, 
	g[25][14]=1, g[25][27]=1, g[25][28]=1, 
	g[29][18]=1, g[29][31]=1, g[29][32]=1, 
	g[33][22]=1, g[33][35]=1, g[33][36]=1, 

	g[2][3]=1, g[2][4]=1, g[2][13]=1, 
	g[6][7]=1, g[6][8]=1, g[6][17]=1, 
	g[10][11]=1, g[10][12]=1, g[10][21]=1, 
	g[14][15]=1, g[14][16]=1, g[14][25]=1, 
	g[18][19]=1, g[18][20]=1, g[18][29]=1, 
	g[22][23]=1, g[22][24]=1, g[22][33]=1, 
	g[26][27]=1, g[26][28]=1, 
	g[30][31]=1, g[30][32]=1, 
	g[34][35]=1, g[34][36]=1, 

	g[3][1]=1, g[3][2]=1, 
	g[15][13]=1, g[15][14]=1, 
	g[27][25]=1, g[27][26]=1, 
	g[7][6]=1, g[7][5]=1, g[7][4]=1, 
	g[19][18]=1, g[19][17]=1, g[19][16]=1, 
	g[31][30]=1, g[31][29]=1, g[31][28]=1, 
	g[11][10]=1, g[11][9]=1, g[11][8]=1, 
	g[23][22]=1, g[23][21]=1, g[23][20]=1, 
	g[35][34]=1, g[35][33]=1, g[35][32]=1, 
	g[4][2]=1, g[4][1]=1, g[4][7]=1, 
	g[16][14]=1, g[16][13]=1, g[16][19]=1, 
	g[28][26]=1, g[28][25]=1, g[28][31]=1, 
	g[8][6]=1, g[8][5]=1, g[8][11]=1, 
	g[20][18]=1, g[20][17]=1, g[20][23]=1, 
	g[32][30]=1, g[32][29]=1, g[32][35]=1, 
	g[12][10]=1, g[12][9]=1, 
	g[24][22]=1, g[24][21]=1, 
	g[36][34]=1, g[36][33]=1;

    for(int i=1; i<=36; ++i){
        G[i].clear();
        for(int j=1; j<=36; ++j)if(g[i][j]){
            G[i].push_back(j);
        }
    }
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/shuangde800/article/details/8741083


, ,