Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

b094. H. 數字拼盤

內容 ：

輸入說明 ：

輸出說明 ：

範例輸入 ：

範例輸出 ：

提示 ：

出處 ：

/**********************************************************************************/
/*  Problem: b094 "H. 數字拼盤" from 2007 NPSC 高中組決賽                */
/*  Language: C                                                                   */
/*  Result: AC (60ms, 246KB) on ZeroJudge                                         */
/*  Author: morris1028 at 2011-07-07 11:37:28                                     */
/**********************************************************************************/


#include<stdio.h>
#include<stdlib.h>
#include<math.h>
struct status {
    int board[3][3];
    int px, py;
}init, target = {1,2,3,4,5,6,7,8,9,2,2};
int pos[10][2], MaxDepth, flag;
int step[4][2] = {{-1,0}, {0,-1},{0,1},{1,0}};/*u l r d*/
void Swap(int *x, int *y) {
    int t;
    t = *x, *x = *y, *y= t;
}
int H() {
    int sum = 0, tmp, a, b;
    for(a = 0; a < 3; a++) {
        for(b = 0; b < 3; b++) {
            tmp = init.board[a][b];
            if(tmp < 9)
                sum += abs(a-pos[tmp][0]) + abs(b-pos[tmp][1]);
        }
    }
    return sum;
}
int SingleH(int x, int y, int tmp) {
    return abs(x-pos[tmp][0]) + abs(y-pos[tmp][1]);
}
int IDAstar(int dv, int hv, int prev) {
    if(hv == 0) { flag = 1;return dv; }
    if(dv + hv > 20 || dv + hv > MaxDepth)    return dv + hv;

    int a, nx, ny, x = init.px, y = init.py;
    int tMaxDepth = 10000, dn, ht;
    
    for(a = 0; a < 4; a++) {
        if(a + prev == 3) continue;
        nx = x + step[a][0], ny = y + step[a][1];
        if(nx < 0 || nx == 3 || ny < 0 || ny == 3)
            continue;
       
        ht = hv - SingleH(nx, ny, init.board[nx][ny]) + SingleH(x, y, init.board[nx][ny]);
        Swap(&init.board[x][y], &init.board[nx][ny]);
        init.px = nx, init.py = ny;
        dn = IDAstar(dv+1, ht, a);
        Swap(&init.board[x][y], &init.board[nx][ny]);
        init.px = x, init.py = y;
        if(flag)    return dv;
        if(tMaxDepth > dn) tMaxDepth = dn;
    }
    return tMaxDepth;
}
main() {
    int T, a, b, ini;
    scanf("%d", &T);
    while(T--) {
        int index = 0;
        for(a = 0; a < 3; a++)
            for(b = 0; b < 3; b++) {
                scanf("%d", &init.board[a][b]);
                if(init.board[a][b] == 0) {
                    init.board[a][b] = 9;
                    init.px = a, init.py = b;
                }
                index++;
                pos[index][0] = a, pos[index][1] = b;
            }
        if(H()) {
            MaxDepth = H(), flag = 0, ini = MaxDepth;
            while((flag == 0) && (MaxDepth <= 20))
                MaxDepth = IDAstar(0, ini, -1);
            puts(flag == 1 ? "Easy" : "Hard");
        }
        else puts("Easy");
    }
    return 0;
}