HDU 1067 Gap

HDU 1067 Gap

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

 

Problem Description - 题目描述

　　Let's play a card game called Gap. 

　　You have 28 cards labeled with two-digit numbers. The first digit (from 1 to 4) represents the suit of the card, and the second digit (from 1 to 7) represents the value of the card.

　　First, you shu2e the cards and lay them face up on the table in four rows of seven cards, leaving a space of one card at the extreme left of each row. The following shows an example of initial layout.

让我们玩个叫Gap的游戏。
你有28个标有两位数的卡片。第一个数（1 ～ 4）表示卡片种类，第二个数（1～7）表示卡片的值。
首先，在桌上摆放四行七列的卡片，每行的最左边留下一张卡片的空位。初始布局如下:

　　Next, you remove all cards of value 1, and put them in the open space at the left end of the rows: "11" to the top row, "21" to the next, and so on.

　　Now you have 28 cards and four spaces, called gaps, in four rows and eight columns. You start moving cards from this layout.

接着，把所有值为1的卡片放到左侧的空位： "11"在最上面，"21"在下一行，以此类推。
现在你有28张卡片与4个空位，共四行八列，并需要从这个布局开始移动卡片。

　　At each move, you choose one of the four gaps and fill it with the successor of the left neighbor of the gap. The successor of a card is the next card in the same suit, when it exists. For instance the successor of "42" is "43", and "27" has no successor.

　　In the above layout, you can move "43" to the gap at the right of "42", or "36" to the gap at the right of "35". If you move "43", a new gap is generated to the right of "16". You cannot move any card to the right of a card of value 7, nor to the right of a gap.

　　The goal of the game is, by choosing clever moves, to make four ascending sequences of the same suit, as follows.

每次移动，你需要选择一个空位，放上空格左边的后续卡。后继卡是同一套牌中的下一张。例如"42"的后继卡为"43"，"27"没有后继卡。

上述布局中，你可以移动"43"至"42"右边的空位，或者移动"36"至"35"右边。若你移动"43"，则有一个新的空位出现在"16"右边。不能移动任何卡片到值为7的卡片右边，也不能移动到空位的右边。

游戏的目标是使用明智移动得出如下四个上升系列。

　　Your task is to find the minimum number of moves to reach the goal layout.

你的目标是找出达成目标布局的最小移动数。

Input - 输入

　　The input starts with a line containing the number of initial layouts that follow.

　　Each layout consists of five lines - a blank line and four lines which represent initial layouts of four rows. Each row has seven two-digit numbers which correspond to the cards.

输入起始行的数字表示初始布局的数量。
每个布局五行 - 一行空，四行初始布局。每行有七个对应卡片的两位数。

 

Output - 输出

　　For each initial layout, produce a line with the minimum number of moves to reach the goal layout. Note that this number should not include the initial four moves of the cards of value 1. If there is no move sequence from the initial layout to the goal layout, produce "-1".

对于每个初始布局，输出一行达成目标布局的最小移动数。注意，这个数不包括值为1卡片的四次初始化移动。如果不存在从初始至目标布局的移动序列，则输出"-1"。

Sample Input - 输入样例

4

12 13 14 15 16 17 21
22 23 24 25 26 27 31
32 33 34 35 36 37 41
42 43 44 45 46 47 11

26 31 13 44 21 24 42
17 45 23 25 41 36 11
46 34 14 12 37 32 47
16 43 27 35 22 33 15

17 12 16 13 15 14 11
27 22 26 23 25 24 21
37 32 36 33 35 34 31
47 42 46 43 45 44 41

27 14 22 35 32 46 33
13 17 36 24 44 21 15
43 16 45 47 23 11 26
25 37 41 34 42 12 31

Sample Output - 输出样例

0
33
60
-1

 

题解

　　BFS + 哈希。

　　之前作死想用map来个暴力判重先试试水，结果不但速度慢，内存直接炸了。

　　然后灵（脑）一光（子）一闪（抽），一个哈希数组坐标，一个哈希数字值，目测出问题的概率不大，A了之后就懒得改了。

 

代码 C++

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <queue>
#define MX 32
#define INF 0x7F7F7F7F
#define LL long long
#define mod 1000007
struct Ary {
    int a[MX], s;
}now, nxt;
int hash[mod], opt, ed[MX] = { 11, 12, 13, 14, 15, 16, 17, 0, 21, 22, 23, 24, 25, 26, 27, 0, 31, 32, 33, 34, 35, 36, 37, 0, 41, 42, 43, 44, 45, 46, 47 };
int getHash_i() {
    LL i, j = 1, rtn;
    for (i = rtn = 0; i < MX; ++i) {
        rtn ^= (j*nxt.a[i]) ^ ed[i];
        j = (j << 1) % mod;
    }
    return rtn%mod;
}
int getHash_v() {
    LL i, j = 1, rtn;
    for (i = rtn = 0; i < MX; ++i) {
        rtn ^= j*(nxt.a[i] ^ ed[i]);
        j = (j << 1) % mod;
    }
    return rtn%mod;
}
bool setHash() {
    for (int i = getHash_i(), v = getHash_v(); i < mod; ++i) {
        if (~hash[i]) {
            if (hash[i] == v) return 0;
        }
        else { hash[i] = v; return 1; }
    }
    return 0;
}
void BFS() {
    int idx[48], zro[4], iz, i, j;
    hash[getHash_i()] = getHash_v();
    std::queue<Ary> q; q.push(nxt);
    while (!q.empty()) {
        now = q.front(); q.pop();
        if (now.s >= opt) continue;
        if (memcmp(now.a, ed, sizeof ed) == 0) {
            opt = std::min(opt, now.s);
            continue;
        }
        ++now.s;
        for (i = iz = 0; i < MX; ++i) {
            (now.a[i] ? idx[now.a[i]] : zro[iz++]) = i;
        }
        for (i = 0; i < 4; ++i) {
            j = zro[i];
            if (now.a[j - 1] % 10 == 7 || !now.a[j - 1]) continue;
            nxt = now;
            nxt.a[j] = now.a[j - 1] + 1;
            nxt.a[idx[nxt.a[j]]] = 0;
            if (setHash()) q.push(nxt);
        }
    }
}
int main() {
    int t, i, j;
    scanf("%d", &t);
    while (t--) {
        memset(hash, -1, sizeof hash); opt = INF;
        for (i = nxt.s = 0, j = 1; i < MX; ++i) {
            if (i % 8) {
                scanf("%d", nxt.a + i);
                if (nxt.a[i] % 10 == 1) nxt.a[i] = 0;
                continue;
            }
            nxt.a[i] = (j += 10);
        }
        BFS();
        printf("%d
", opt == INF ? -1 : opt);
    }
    return 0;
}