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

49愛的鼓勵 6訂閱站台

內容 ：

輸入說明 ：

輸出說明 ：

範例輸入 ：

範例輸出 ：

提示 ：

出處 ：

/**********************************************************************************/
/*  Problem: d207 "15 - Puzzle" from Uva Online Judge  Q10181                     */
/*  Language: CPP (3255 Bytes)                                                    */
/*  Result: AC(2s, 254KB) judge by this@ZeroJudge                                 */
/*  Author: morris1028 at 2012-11-26 19:56:16                                     */
/**********************************************************************************/


#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#define LLU unsigned long long
using namespace std;
struct status {
    char board[4][4];
    int ix, iy;
} init;
int pos[16][2], mxdep;
int dir[4][2] = {{0,-1},{-1,0},{1,0},{0,1}};/*u,l,r,d*/
char dirc[4] = {'L', 'U', 'D', 'R'}, path[100];
int solved;
bool solvable() {
    int sum = 0, row, i, j;
    for(i = 0; i < 16; i++) {
        if(init.board[i/4][i%4] == 0) {
            row = i/4 + 1;
            continue;
        }
        for(j = i+1; j < 16; j++) {
            if(init.board[j/4][j%4] < init.board[i/4][i%4]) {
                if(init.board[j/4][j%4])
                    sum++;
            }
        }
    }
    return 1-(sum+row)%2;
}
int H() {
    static int i, j, sum, num;
    sum = 0;
    for(i = 0; i < 4; i++) {
        for(j = 0; j < 4; j++) {
            num = init.board[i][j];
            if(num == 0)
                continue;
            sum += abs(i-pos[num][0]) + abs(j-pos[num][1]);
        }
    }
    return sum;
}
int Htable[4][4][16];
int IDA(int dep, int hv, int prestep) {
    if(hv == 0) {
        solved = dep;
       /* path[dep] = '\0';
        puts(path);*/
        return dep;
    }
    if(dep + 114*hv/100 > mxdep) {
        return dep + 114*hv/100;
    }
    int i, tx, ty, x = init.ix, y = init.iy;
    int submxdep = 0xfff, val = 0xfff, shv;

    for(i = 0; i < 4; i++) {
        if(i + prestep == 3)    continue;
        tx = x + dir[i][0], ty = y + dir[i][1];
        if(tx < 0 || ty < 0 || tx > 3 || ty > 3)
            continue;

        shv = hv;
        shv -= Htable[tx][ty][init.board[tx][ty]];
        shv += Htable[x][y][init.board[tx][ty]];
        init.ix = tx, init.iy = ty;
        swap(init.board[x][y], init.board[tx][ty]);

        path[dep] = dirc[i];
        val = IDA(dep+1, shv, i);

        swap(init.board[x][y], init.board[tx][ty]);
        init.ix = x, init.iy = y;
        if(solved)  return solved;
        submxdep = min(submxdep, val);
    }
    return submxdep;
}
int main() {
    int test, i, j, k, initH;
    int cases = 0;
    for(i = 0, k = 0; i < 4; i++)
        for(j = 0; j < 4; j++)
            pos[++k][0] = i, pos[k][1] = j;
    for(i = 0; i < 4; i++)
        for(j = 0; j < 4; j++)
            for(k = 1; k < 16; k++)
                Htable[i][j][k] = abs(i - pos[k][0]) + abs(j - pos[k][1]);
    scanf("%d", &test);
    while(test--) {
        cases++;
        for(i = 0; i < 4; i++) {
            for(j = 0; j < 4; j++) {
                scanf("%d", &k);
                init.board[i][j] = k;
                if(init.board[i][j] == 0) {
                    init.ix = i, init.iy = j;
                }
            }
        }
        if(solvable()) {
            solved = 0, initH = mxdep = H();
            if(!mxdep) {
                puts("0");
                continue;
            }
            while(solved == 0)
                mxdep = IDA(0, initH, -1);
            printf("%d\n", solved);
        }else {
            puts("This puzzle is not solvable.");
        }
    }
    return 0;
}
/*
2
6 2 8 4
12 14 1 10
13 15 3 9
11 0 5 7
0 1 3 8
5 7 4 6
9 2 10 11
13 14 15 12
*/