HDU 2234 无题I-白红宇

HDU 2234 无题I

阅读量：5094 次

发布时间：2019-06-13

本文共 3574 字，大约阅读时间需要 11 分钟。

HDU_2234

这个题目可以先从终态出发，把5步以内的所有状态预处理出来，同时为了进一步减少状态，利用最小表示法的思想，将终态看成只有两种：

1111

2222

3333

4444

和

1234

，这样我的程序最终跑出来就只有157370个状态了。

在查询的时候，由于前面我们用最小表示法将状态简化了，那么现在就要将1、2、3、4全排列一下生成24种状态，每种状态都查找一下，然后取这24种状态下的最小值。

#include
     
      #include
      
       #include
       
        #define HASH 1000007#define MAXD 1000010#define INF 0x3f3f3f3ftypedef unsigned int _int;struct HashMap{    int head[HASH], size, next[MAXD];    _int st[MAXD];    void init()    {        memset(head, -1, sizeof(head));        size = 0;    }    int find(_int _st)    {        int i, h = _st % HASH;        for(i = head[h]; i != -1; i = next[i])            if(st[i] == _st) break;        return i;        }    void push(_int _st)    {        int h = _st % HASH;            st[size] = _st;        next[size] = head[h], head[h] = size ++;    }}hm;int trans[][4] ={    {
    0, 1, 2, 3}, {
   0, 1, 3, 2}, {
   0, 2, 1, 3}, {
   0, 2, 3, 1}, {
   0, 3, 1, 2}, {
   0, 3, 2, 1},    {
    1, 0, 2, 3}, {
   1, 2, 0, 3}, {
   1, 2, 3, 0}, {
   1, 0, 3, 2}, {
   1, 3, 0, 2}, {
   1, 3, 2, 0},    {
    2, 0, 1, 3}, {
   2, 0, 3, 1}, {
   2, 1, 0, 3}, {
   2, 1, 3, 0}, {
   2, 3, 0, 1}, {
   2, 3, 1, 0},    {
    3, 0, 1, 2}, {
   3, 0, 2, 1}, {
   3, 1, 0, 2}, {
   3, 1, 2, 0}, {
   3, 2, 0, 1}, {
   3, 2, 1, 0},};_int q[MAXD];int  dis[MAXD], code[4][4];_int encode(int code[][4]){    int i, j;    _int ans = 0;    for(i = 0; i < 4; i ++)        for(j = 0; j < 4; j ++) ans = ans << 2 | code[i][j];    return ans;}void decode(_int st){    int i, j;    for(i = 3; i >= 0; i --)        for(j = 3; j >= 0; j --) code[i][j] = st & 3, st >>= 2;}void shr(int r, int k){    int i;    if(k == 0) for(i = 0; i < 3; i ++) std::swap(code[r][i], code[r][i + 1]);    else for(i = 3; i >= 1; i --) std::swap(code[r][i], code[r][i - 1]);}void shc(int c, int k){    int i;    if(k == 0) for(i = 0; i < 3; i ++) std::swap(code[i][c], code[i + 1][c]);    else for(i = 3; i >= 1; i --) std::swap(code[i][c], code[i - 1][c]);    }void prepare(){    int i, j, k, rear = 0;    _int x, y;    hm.init();    for(i = 0; i < 4; i ++)        for(j = 0; j < 4; j ++) code[i][j] = i;    x = encode(code);    hm.push(x), q[rear ++] = x;    for(i = 0; i < 4; i ++)        for(j = 0; j < 4; j ++) code[i][j] = j;    x = encode(code);    hm.push(x), dis[rear] = 0, q[rear ++] = x;    for(i = 0; i < rear; i ++)    {        if(dis[i] >= 5) continue;        x = q[i];        decode(x);        for(j = 0; j < 4; j ++)            for(k = 0; k < 2; k ++)            {                shr(j, k);                y = encode(code);                if(hm.find(y) == -1)                    hm.push(y), dis[rear] = dis[i] + 1, q[rear ++] = y;                shr(j, k ^ 1);                shc(j, k);                y = encode(code);                if(hm.find(y) == -1)                    hm.push(y), dis[rear] = dis[i] + 1, q[rear ++] = y;                shc(j, k ^ 1);                }        }    //printf(">> %d\n", rear);}void solve(){    int i, j, k, g[4][4], ans = INF;    for(i = 0; i < 4; i ++)        for(j = 0; j < 4; j ++) scanf("%d", &g[i][j]), -- g[i][j];    for(k = 0; k < 24; k ++)    {        for(i = 0; i < 4; i ++)            for(j = 0; j < 4; j ++) code[i][j] = trans[k][g[i][j]];        i = hm.find(encode(code));        if(i != -1) ans = std::min(ans, dis[i]);    }    if(ans == INF) printf("-1\n");    else printf("%d\n", ans);}int main(){    prepare();    int t;    scanf("%d", &t);    while(t --)        solve();    return 0;    }

转载于:https://www.cnblogs.com/staginner/archive/2012/08/28/2660223.html

你可能感兴趣的文章