2012-11-27 08:33:21Morris
[ZJ][IDA*] d207. 15 - Puzzle
內容 ：
15-puzzle 是一個廣受歡迎的遊戲，就算你光從字面上可能不知道 15-puzzle 是什麼，但是你一定看過。
這遊戲是由 15 個可滑動的方塊組合成的，分別標上 1 ~ 15 的數字，然後擺在一個 4 x 4 大小的框架中， ( 當然有一個格子是空的 ) 。
這個遊戲的目的就是將所有方塊移動成如下的樣子：
| 一個隨機的盤面。 | 將空格向右移。 |
| 將空格向上移。 | 將空格向左移。 |
如果這個盤面無解，請輸出一行 This puzzle is not solvable.
輸入說明
：
第一行有一個正整數 T 代表以下有 T 組測資，
每組測資為 4 x 4 的方陣，由 0 ~ 15 組成，其中 0 代表 puzzle 的空格。
輸出說明
：
對每組測資，輸出一行。
若有解的話，請出輸出最少要幾步才能將起始盤面變換成目標盤面。
若無解，請輸出 This puzzle is not solvable.
注意：本題答案有可能超過 50 步，和 Uva 之要求不盡相同。
範例輸入
：
2 2 3 4 0 1 5 7 8 9 6 10 12 13 14 11 15 13 1 2 4 5 0 3 7 9 6 10 12 15 8 11 14
範例輸出 ：
9 This puzzle is not solvable.
提示
：
背景知識：
哈電族 - 華容道
先玩玩哈電族的華容道吧!
先玩玩哈電族的華容道吧!
出處
：
Uva Online Judge Q10181
(管理：VacationClub)
今晚的研究課題「常數的力量」
先講講 UVa 10181 - 15-Puzzle Problem，題目要求不難，測資只會有 50 步以內的解法，而討論區有提供 50 步以上的測資，小弟我測了一下，居然跑出了 48 步的解答，當下愣了許久，但模擬一次也沒錯。
第一次上傳跑了快一秒。
之後為了解決 ZEROJUDGE 中大神們丟出的 「d207. 15 - Puzzle」小弟我不斷地測修改啟發式函數的常數，一修再修，最後二分搜常數，終於過了 ...。
之後再丟丟 UVa 得到了嚇人的 0.008 s，這神馬情況，居然快了十多倍，常數的力量果然不可小覷。 <(_ _)>
今晚的研究課題「常數的力量」
先講講 UVa 10181 - 15-Puzzle Problem，題目要求不難，測資只會有 50 步以內的解法，而討論區有提供 50 步以上的測資，小弟我測了一下，居然跑出了 48 步的解答，當下愣了許久，但模擬一次也沒錯。
第一次上傳跑了快一秒。
之後為了解決 ZEROJUDGE 中大神們丟出的 「d207. 15 - Puzzle」小弟我不斷地測修改啟發式函數的常數，一修再修，最後二分搜常數，終於過了 ...。
之後再丟丟 UVa 得到了嚇人的 0.008 s，這神馬情況，居然快了十多倍，常數的力量果然不可小覷。 <(_ _)>
/**********************************************************************************/
/* 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
*/