2011-09-10 14:25:03Morris
d733. 11329 - Curious Fleas
d733. 11329 - Curious Fleas
內容 ：
你最珍貴的財產就是你的跳蚤馬戲團。主要的吸引力是這個馬戲團的六隻雜技跳蚤在表演。有一天你不小心打翻裝有這些跳蚤的容器，它們都佔據了整個 4x4的正方形瓷磚，充滿了您的廚房的地板。出乎意料的是，沒有兩隻相同的跳蚤在正方形瓷磚上。
你 的兒子安迪有一個六個面正常的骰子，骰子每個面都和正方形瓷磚一樣大。你決定要玩一個遊戲。首先，您的骰子恰好在一個沒有跳蚤的瓷磚。然後你開始滾動骰子 到邊緣任何一個的相鄰瓷磚。跳蚤們是非常好奇，他們喜歡探索。當您移動骰子到一個包含跳蚤的正方形瓷磚，跳蚤就會跳躍到骰子的底部。跳蚤是小到足夠隱藏在 骰子上的點，所以他們在這個過程中並不會死。同樣地，如果跳蚤所在的那一面翻轉到地板上時，它就會跳躍到正方形瓷磚上。
你的遊戲的目標是將翻轉骰子到所有的跳蚤都在骰子上時，就算是結束。骰子不能離開你的廚房當中的4x4格子。以下的圖片是一個範例同時也是第一筆測資：
第一行顯示的數字表示接下來有幾筆的測試資料。每個測試資料包括一個空行和四行且每行皆有四個字元描述著初始盤面。'.'表示空格、'X'表示一隻跳蚤、'D'表示骰子的初始位置。而且每一筆測試資料都一定會有一個骰子和六隻跳蚤。
對於每個測試資料，輸出一行包含一個數字為最少翻轉的次數，必須在同一時間點每一個面都要有一隻跳蚤才算結束。如果測試資料無法解決，輸出"impossible"。
輸入說明
：
輸出說明
：
範例輸入 ：
2 ...X XXXX D..X .... DX.X .X.. ..X. X..X
範例輸出 ：
8 14
提示
：
如果UVA想衝排名這題是很不錯的選擇~~只要有1秒就可以進了！
譯：asas
出處
：
11329 - Curious Fleas
(管理：asas)
作法 : 從最終的狀態開始導推回去, 直接建表
盤面跳蚤的總情形 2^16, 骰子的位置 16 種, 骰子上有沒有跳蚤的狀態 2^6
總計, 分成 2^26 次方, 盤面切割成 0 ~ 15
00 01 02 03
04 05 06 07
08 09 10 11
12 13 14 15
1111 | 1111 | 1111 | 1111 | 1111 | 111111 => 當作一個數字
(15~12)(11~8) (7~4) (3~1)(骰子位置)(骰子六面有無跳蚤)
111111 骰子面 : 前後左右上下
作法 : 從最終的狀態開始導推回去, 直接建表
盤面跳蚤的總情形 2^16, 骰子的位置 16 種, 骰子上有沒有跳蚤的狀態 2^6
總計, 分成 2^26 次方, 盤面切割成 0 ~ 15
00 01 02 03
04 05 06 07
08 09 10 11
12 13 14 15
1111 | 1111 | 1111 | 1111 | 1111 | 111111 => 當作一個數字
(15~12)(11~8) (7~4) (3~1)(骰子位置)(骰子六面有無跳蚤)
111111 骰子面 : 前後左右上下
※ 盤面上絕對不會多於 6 隻跳蚤, 因此狀態總個數
[C(16, 0) + .. + C(16, 6)] * 16 * (2^6) = 10777600
又, 一定會有無解的盤面, 因此會更少
/**********************************************************************************/
/* Problem: d733 "11329 - Curious Fleas" from 11329 - Curious Fleas */
/* Language: C */
/* Result: AC(344ms, 72.7MB) judge by this@ZeroJudge */
/* Author: morris1028 at 2011-09-10 11:10:32 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define total_state 67108864
#define init 0
char DP[total_state+1];
int Queue[1760896], Qt = -1;
int min(int x, int y) {
if(x == 0) return y;
if(y == 0) return x;
return x < y ? x : y;
}
void Front_turn(int state) {
static int change_state, t1, t2, dice;
t1 = state&63;
dice = t1&12;/*001100*/
dice |= ((t1&32) != 0) | (((t1&16) != 0)<<1) | (((t1&2) != 0)<<5) | (((t1&1) != 0)<<4);
t1 = (state>>6)&15, t2 = t1;
if(t1 >= 12 && t1 <= 15) return;
t1 += 4;
change_state = dice | ((state>>10)<<10) | (t1<<6);
if((state&1) != 0 && (state&(1<<(t2+10))) == 0)
change_state = (change_state | (1<<(t2+10))) - (1<<4);
else if((state&1) == 0 && (state&(1<<(t2+10))) != 0)
change_state = (change_state - (1<<(t2+10))) | (1<<4);
if(DP[change_state] == init)
Queue[++Qt] = change_state;
DP[change_state] = min(DP[change_state], DP[state]+1);
}
void Back_turn(int state) {
static int change_state, t1, t2, dice;
t1 = state&63;
dice = t1&12;/*001100*/
dice |= (((t1&32) != 0)<<1) | ((t1&16) != 0) | (((t1&2) != 0)<<4) | (((t1&1) != 0)<<5);
/*new dice set*/
t1 = (state>>6)&15, t2 = t1;
if(t1 >= 0 && t1 <= 3) return;
t1 -= 4;
change_state = dice | ((state>>10)<<10) | (t1<<6);
if((state&1) != 0 && (state&(1<<(t2+10))) == 0)
change_state = (change_state | (1<<(t2+10))) - (1<<5);
else if((state&1) == 0 && (state&(1<<(t2+10))) != 0)
change_state = (change_state - (1<<(t2+10))) | (1<<5);
if(DP[change_state] == init)
Queue[++Qt] = change_state;
DP[change_state] = min(DP[change_state], DP[state]+1);
}
void Right_turn(int state) {
static int change_state = 0, t1, t2, dice;
t1 = state&63;
dice = t1&48;/*110000*/
dice |= (((t1&8) != 0)<<1) | (((t1&4) != 0)) | (((t1&2) != 0)<<2) | (((t1&1) != 0)<<3);
t1 = (state>>6)&15, t2 = t1;
if(t1 == 3 || t1 == 7 || t1 == 11 || t1 == 15) return;
t1 += 1;
change_state = dice | ((state>>10)<<10) | (t1<<6);
if((state&1) != 0 && (state&(1<<(t2+10))) == 0)
change_state = (change_state | (1<<(t2+10))) - (1<<3);
else if((state&1) == 0 && (state&(1<<(t2+10))) != 0)
change_state = (change_state - (1<<(t2+10))) | (1<<3);
if(DP[change_state] == init)
Queue[++Qt] = change_state;
DP[change_state] = min(DP[change_state], DP[state]+1);
}
void Left_turn(int state) {
static int change_state = 0, t1, t2, dice;
t1 = state&63;
dice = t1&48;/*110000*/
dice |= (((t1&8) != 0)) | (((t1&4) != 0)<<1) | (((t1&2) != 0)<<3) | (((t1&1) != 0)<<2);
t1 = (state>>6)&15, t2 = t1;
if(t1 == 0 || t1 == 4 || t1 == 8 || t1 == 12) return;
t1 -= 1;
change_state = dice | ((state>>10)<<10) | (t1<<6);
if((state&1) != 0 && (state&(1<<(t2+10))) == 0)
change_state = (change_state | (1<<(t2+10))) - (1<<2);
else if((state&1) == 0 && (state&(1<<(t2+10))) != 0)
change_state = (change_state - (1<<(t2+10))) | (1<<2);
if(DP[change_state] == init)
Queue[++Qt] = change_state;
DP[change_state] = min(DP[change_state], DP[state]+1);
}
void process() {
memset(DP, init, sizeof(DP));
int i, j;
for(i = 0; i <= 15; i++)
for(j = 0; j <= 63; j++) {
DP[(i<<6) | j] = 1;
Queue[++Qt] = (i<<6) | j;
}
int now;
for(i = 0; i <= Qt; i++) {
now = Queue[i];
Front_turn(now);
Back_turn(now);
Right_turn(now);
Left_turn(now);
}
}
main() {
process();
int t;
char s[5];
scanf("%d", &t);
while(t--) {
int i, j, state = 0;
for(i = 0; i < 4; i++) {
scanf("%s", s);
for(j = 0; j < 4; j++) {
if(s[j] == 'X')
state |= (1<<(i*4+j+10));
if(s[j] == 'D')
state += (1<<6)*(i*4+j);
}
}
if(DP[state] == init)
puts("impossible");
else
printf("%d\n", DP[state]-1);
}
return 0;
}
因為真正的狀態其實很少, 用了下雜湊表
但並沒有比較快, 記憶體比較小而已
/**********************************************************************************/
/* Problem: d733 "11329 - Curious Fleas" from 11329 - Curious Fleas */
/* Language: C */
/* Result: AC(1.2s, 31.2MB) judge by this@ZeroJudge */
/* Author: morris1028 at 2011-09-10 14:12:03 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#define HAND 876543
struct {
int state, next;
char Ans;
}NODE[1760900];
int size = 1, HASH[HAND+1];
int Queue[1760896], Qt = -1;
char Min(char x, char y) {
return x < y ? x : y;
}
void FreeAll() {
int i;
for(i = 0, size = 1; i <= HAND; i++)
HASH[i] = 0;
}
char insHASH(int state, char Ans) {
static int m, pre, now;
m = state%HAND;
pre = 0, now = HASH[m];
while(now) {
if(NODE[now].state == state) {
NODE[now].Ans = Min(NODE[now].Ans, Ans);
return 1;
} else if(NODE[now].state < state) {
pre = now, now = NODE[now].next;
}
else break;
}
NODE[size].Ans = Ans, NODE[size].state = state;
NODE[size].next = now;
if(pre) NODE[pre].next = size;
else HASH[m] = size;
size++;
return 0;
}
char findHASH(int state) {
static int m, pre, now;
m = state%HAND;
pre = 0, now = HASH[m];
while(now) {
if(NODE[now].state == state) {
return NODE[now].Ans;
} else if(NODE[now].state < state) {
pre = now, now = NODE[now].next;
}
else break;
}
return -1;
}
void Front_turn(int state, int step) {
static int change_state, t1, t2, dice;
t1 = state&63;
dice = t1&12;/*001100*/
dice |= ((t1&32) != 0) | (((t1&16) != 0)<<1) | (((t1&2) != 0)<<5) | (((t1&1) != 0)<<4);
t1 = (state>>6)&15, t2 = t1;
if(t1 >= 12 && t1 <= 15) return;
t1 += 4;
change_state = dice | ((state>>10)<<10) | (t1<<6);
if((state&1) != 0 && (state&(1<<(t2+10))) == 0)
change_state = (change_state | (1<<(t2+10))) - (1<<4);
else if((state&1) == 0 && (state&(1<<(t2+10))) != 0)
change_state = (change_state - (1<<(t2+10))) | (1<<4);
if(insHASH(change_state, step) == 0)
Queue[++Qt] = change_state;
}
void Back_turn(int state, int step) {
static int change_state, t1, t2, dice;
t1 = state&63;
dice = t1&12;/*001100*/
dice |= (((t1&32) != 0)<<1) | ((t1&16) != 0) | (((t1&2) != 0)<<4) | (((t1&1) != 0)<<5);
t1 = (state>>6)&15, t2 = t1;
if(t1 >= 0 && t1 <= 3) return;
t1 -= 4;
change_state = dice | ((state>>10)<<10) | (t1<<6);
if((state&1) != 0 && (state&(1<<(t2+10))) == 0)
change_state = (change_state | (1<<(t2+10))) - (1<<5);
else if((state&1) == 0 && (state&(1<<(t2+10))) != 0)
change_state = (change_state - (1<<(t2+10))) | (1<<5);
if(insHASH(change_state, step) == 0)
Queue[++Qt] = change_state;
}
void Right_turn(int state, int step) {
static int change_state = 0, t1, t2, dice;
t1 = state&63;
dice = t1&48;/*110000*/
dice |= (((t1&8) != 0)<<1) | (((t1&4) != 0)) | (((t1&2) != 0)<<2) | (((t1&1) != 0)<<3);
t1 = (state>>6)&15, t2 = t1;
if(t1 == 3 || t1 == 7 || t1 == 11 || t1 == 15) return;
t1 += 1;
change_state = dice | ((state>>10)<<10) | (t1<<6);
if((state&1) != 0 && (state&(1<<(t2+10))) == 0)
change_state = (change_state | (1<<(t2+10))) - (1<<3);
else if((state&1) == 0 && (state&(1<<(t2+10))) != 0)
change_state = (change_state - (1<<(t2+10))) | (1<<3);
if(insHASH(change_state, step) == 0)
Queue[++Qt] = change_state;
}
void Left_turn(int state, int step) {
static int change_state = 0, t1, t2, dice;
t1 = state&63;
dice = t1&48;/*110000*/
dice |= (((t1&8) != 0)) | (((t1&4) != 0)<<1) | (((t1&2) != 0)<<3) | (((t1&1) != 0)<<2);
t1 = (state>>6)&15, t2 = t1;
if(t1 == 0 || t1 == 4 || t1 == 8 || t1 == 12) return;
t1 -= 1;
change_state = dice | ((state>>10)<<10) | (t1<<6);
if((state&1) != 0 && (state&(1<<(t2+10))) == 0)
change_state = (change_state | (1<<(t2+10))) - (1<<2);
else if((state&1) == 0 && (state&(1<<(t2+10))) != 0)
change_state = (change_state - (1<<(t2+10))) | (1<<2);
if(insHASH(change_state, step) == 0)
Queue[++Qt] = change_state;
}
void process() {
FreeAll();
int i, j, now, step, k;
for(i = 0; i <= 15; i++)
for(j = 0; j <= 63; j++) {
k = (i<<6) | j;
insHASH(k, 0);
Queue[++Qt] = k;
}
for(i = 0; i <= Qt; i++) {
now = Queue[i], step = findHASH(now)+1;
Front_turn(now, step);
Back_turn(now, step);
Right_turn(now, step);
Left_turn(now, step);
}
}
main() {
process();
int t;
char s[5];
scanf("%d", &t);
while(t--) {
int i, j, state = 0;
for(i = 0; i < 4; i++) {
scanf("%s", s);
for(j = 0; j < 4; j++) {
if(s[j] == 'X')
state |= (1<<(i*4+j+10));
if(s[j] == 'D')
state += (1<<6)*(i*4+j);
}
}
if(findHASH(state) == -1)
puts("impossible");
else
printf("%d\n", findHASH(state));
}
return 0;
}