HDU 1043 Eight（八數(shù)碼）

Time?Limit:?10000/5000?MS?(Java/Others)????Memory?Limit:?65536/32768?K?(Java/Others)

?

Problem?Description - 題目描述 　　The 15-puzzle has been around for over 100 years; even if you don't know it by that name, you've seen it. It is constructed with 15 sliding tiles, each with a number from 1 to 15 on it, and all packed into a 4 by 4 frame with one tile missing. Let's call the missing tile 'x'; the object of the puzzle is to arrange the tiles so that they are ordered as: 15-puzzle有著超過100年的歷史；就算沒聽過，估計也見過。它由15片滑塊組成，各塊標(biāo)有數(shù)字1到15，并且全都裝在一個4 x 4的邊框里，防止哪塊突然丟了。空塊為’x’；這道題的目標(biāo)是排列滑塊使之順序如下： CN

?

1 2 3 45 6 7 89 10 11 12 13 14 15 x

　　where the only legal operation is to exchange 'x' with one of the tiles with which it shares an edge. As an example, the following sequence of moves solves a slightly scrambled puzzle:

唯一的合法操作是將’x’與其共邊的滑塊交換。例子如下，通過一系列移動解決一個被稍微打亂的問題。 CN

?

1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 45 6 7 8 5 6 7 8 5 6 7 8 5 6 7 89 x 10 12 9 10 x 12 9 10 11 12 9 10 11 12 13 14 11 15 13 14 11 15 13 14 x 15 13 14 15 xr-> d-> r->

?

　　The letters in the previous row indicate which neighbor of the 'x' tile is swapped with the 'x' tile at each step; legal values are 'r','l','u' and 'd', for right, left, up, and down, respectively.

　　Not all puzzles can be solved; in 1870, a man named Sam Loyd was famous for distributing an unsolvable version of the puzzle, and frustrating many people. In fact, all you have to do to make a regular puzzle into an unsolvable one is to swap two tiles (not counting the missing 'x' tile, of course).

　　In this problem, you will write a program for solving the less well-known 8-puzzle, composed of tiles on a three by three arrangement.

上一行的字母表示每次’x’與哪塊相鄰的滑塊交換；有效值'r'，'l'，'u' 和 'd'分別表示右、左、上、下。并非所有情況都有解；在1870年，一個叫Sam Loyd的人就以發(fā)布了一個無解版本而出名，成功地難住了許多人。實際上，要制造無解的情況只需交換兩個滑塊（當(dāng)然是非’x’滑塊）。這個問題中，你需要寫個程序解決著名的八數(shù)碼問題，滑塊為三行三列。 CN

?

Input - 輸入

　　You will receive, several descriptions of configuration of the 8 puzzle. One description is just a list of the tiles in their initial positions, with the rows listed from top to bottom, and the tiles listed from left to right within a row, where the tiles are represented by numbers 1 to 8, plus 'x'. For example, this puzzle

1 2 3

x 4 6

7 5 8

　　is described by this list:

1 2 3 x 4 6 7 5 8

你會得到若干個八數(shù)碼的配置描述。每個描述都是一個滑塊初始位置的列表，從上往下，從左往右，使用數(shù)字1到8，還有’x’表示。比如，1 2 3 x 4 6 7 5 8 描述如下：1 2 3 x 4 6 7 5 8 CN

Output -?輸出

　　You will print to standard output either the word ``unsolvable'', if the puzzle has no solution, or a string consisting entirely of the letters 'r', 'l', 'u' and 'd' that describes a series of moves that produce a solution. The string should include no spaces and start at the beginning of the line. Do not print a blank line between cases. 如果無解，輸出”unsolvable''”，否則輸出一個僅由'r', 'l', 'u' 和 'd' 組成的字符串，描述求解的步驟。這個字符串不含空格且單獨在一行。用例間別輸出空行。 CN

?

Sample?Input - 輸入樣例

2 3 4 1 5 x 7 6 8

?

Sample?Output -?輸出樣例

ullddrurdllurdruldr

?

題解
　　逼你學(xué)新知識系列……（某廢渣作死爆內(nèi)存了……）
　　狀態(tài)可以用全排列表示，用康托展開來壓縮狀態(tài)和去重，然后剩下的只有BFS了……（無聊用了樹狀數(shù)組求逆序數(shù)）
　　多組輸入有點坑……其實如果符合情況直接輸出空行也是可以的。

?

代碼?C++

1 #include <cstdio> 2 #include <cstring> 3 #include <queue> 4 #define MX 362880 5 #define bitMX 10 6 7 int tre[bitMX]; 8 int lowBit(int a) { return -a&a; } 9 void add(int i) { 10 while (i < bitMX) { ++tre[i]; i += lowBit(i); } 11 } 12 int sum(int i) { 13 int opt = 0; 14 while (i) { opt += tre[i]; i -= lowBit(i); } 15 return opt; 16 } 17 18 int ktf[9], data[9]; 19 int preKte() { 20 int i, j, opt = 0; 21 memset(tre, 0, sizeof tre); 22 for (i = 8; ~i; --i) { 23 opt += sum(data[i])*ktf[i]; 24 add(data[i]); 25 } 26 return opt; 27 } 28 void kte(int a) { 29 int i, j, tmp[9]; 30 for (i = 0; i < 9; ++i) tmp[i] = i + 1; 31 for (i = 0; i < 8; ++i) { 32 j = a / ktf[i]; a %= ktf[i]; 33 data[i] = tmp[j]; 34 memcpy(tmp + j, tmp + j + 1, sizeof(int)*(8 - j)); 35 } 36 data[i] = tmp[0]; 37 } 38 39 int lst[MX]; 40 char pre[MX]; 41 void push(int now, int i, int j, char c, std::queue<int> &q) { 42 data[i] ^= data[j]; data[j] ^= data[i]; data[i] ^= data[j]; 43 int nxt = preKte(); 44 if (!pre[nxt]) { 45 lst[nxt] = now; pre[nxt] = c; 46 q.push(nxt); 47 } 48 data[i] ^= data[j]; data[j] ^= data[i]; data[i] ^= data[j]; 49 } 50 void init() { 51 int i, j, now, nxt; 52 ktf[7] = 1; 53 for (i = 6, j = 2; ~i; --i, ++j) ktf[i] = ktf[i + 1] * j; 54 memset(lst, -1, sizeof lst); 55 lst[0] = 0; pre[0] = ' '; 56 std::queue<int> q; q.push(0); 57 while (!q.empty()) { 58 now = q.front(); q.pop(); 59 kte(now); 60 for (i = 0; data[i] != 9; ++i); 61 if (i > 2) push(now, i, i - 3, 'd', q); 62 if (i < 6) push(now, i, i + 3, 'u', q); 63 if (i % 3) push(now, i, i - 1, 'r', q); 64 if ((i + 1) % 3) push(now, i, i + 1, 'l', q); 65 } 66 67 68 } 69 int main() { 70 init(); 71 int i, j; 72 char red[18]; 73 while (gets(red)) { 74 for (i = j = 0; i < 18; i += 2, ++j) data[j] = red[i] == 'x' ? 9 : red[i] - '0'; 75 if (~lst[i = preKte()]) { 76 for (j = i; j; j = lst[j]) putchar(pre[j]); 77 puts(""); 78 } 79 else puts("unsolvable"); 80 } 81 return 0; 82 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Simon-X/p/6701038.html

總結(jié)

以上是生活随笔為你收集整理的HDU 1043 Eight（八数码）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。