2011-07-09 05:57:34Morris
b094. H. 數字拼盤 (IDA* 版本)
b094. H. 數字拼盤
內容 ：
數字拼盤是個很古老的遊戲，由Sam Loyd在1870年左右所發明，盤面由一個九宮格構成，上面有八個可移動的方塊，分別是編號1到8，遊戲的目的是要藉由移動這八個方塊，使盤面回到最初的狀態也就是八個方塊依照數字排序，而方塊只能往空格的地方移動。
圖一
以上圖為例，這個盤面可移動的方塊有兩種選擇，分別是2 (可往下移動)以及3 (可往右移動)。而盤面終止的條件為數字1在左上角、數字2在正上方、數字3在右上角、數字4在最左邊、數字5在中間、數字6在最右邊、數字7在左下角、數字8在正下方、而空格在右下方，如下圖：
圖二
小達達的媽媽送了他一個數字拼盤，但正如名字一般，小達達的頭腦阿達阿達的，他把拼盤打亂後根本不知道要如何把拼盤弄回來，有一天他帶著數字拼盤到學校的時候，恰好被班上成績最好的同學小君君看到，小君君看著他的數字拼盤說：”這麼簡單的遊戲，我20步以內就能解出來了”。小達達聽了很不甘心，他決定要找出無法20步之內解出來的狀態。
輸入說明
：
輸入檔中會有多筆資料，第一行是一個正整數k，代表一共有多少組資料，接下來是k組測試資料，每組測試資料有三行，每行三個用空白隔開的數字代表數字拼盤的盤面狀態，其中0代表空格的位置。
輸出說明
：
對每組測試資料，如果這組測試資料能夠在20步以內被解出來，請輸出Easy，其餘的狀況請輸出Hard，。
範例輸入 ：
2 1 2 3 4 5 6 8 7 0 1 2 3 4 5 6 7 0 8
範例輸出 ：
Hard Easy
提示
：
出處
：
2007 NPSC 高中組決賽
作法 : IDA*
跟 A* 的差別就是少一個 heap去抓最小值出來擴張，因此會重複走點
15 數碼，只能用 IDA* ，A* 會記憶體爆炸
IDA*(Iterative deepening A*)即是迭代加深启发式搜索.在这题当中,实际上是把启发函数用来做剪枝了,算法如下:
1.定义启发函数 H()为∑[abs(xInit-xTarget)+abs(yInit-yTarget)],由于每次移动H值最多少1,所以它是相容的.
2.设初始迭代深度为初始状态的H值 H(initStatus);
3.迭代加深进行搜索.
4.如果 当前搜索深度 + H值 > 迭代深度,则剪枝.
作法 : IDA*
跟 A* 的差別就是少一個 heap去抓最小值出來擴張，因此會重複走點
15 數碼，只能用 IDA* ，A* 會記憶體爆炸
IDA*(Iterative deepening A*)即是迭代加深启发式搜索.在这题当中,实际上是把启发函数用来做剪枝了,算法如下:
1.定义启发函数 H()为∑[abs(xInit-xTarget)+abs(yInit-yTarget)],由于每次移动H值最多少1,所以它是相容的.
2.设初始迭代深度为初始状态的H值 H(initStatus);
3.迭代加深进行搜索.
4.如果 当前搜索深度 + 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;
}
上一篇：b254. C. 矢量星球
下一篇：b018. F. 營地