Posted on 2008-10-16 09:19
歲月流逝 閱讀(114)
評(píng)論(0) 編輯 收藏 引用
題目描述：
八方塊移動(dòng)游戲要求從一個(gè)含8個(gè)數(shù)字（用1-8表示）的方塊以及一個(gè)空格方塊（用0表示）的3x3矩陣的起始狀態(tài)開始，不斷移動(dòng)該空格方塊以使其和相鄰的方塊互換，直至達(dá)到所定義的目標(biāo)狀態(tài)。空格方塊在中間位置時(shí)有上、下、左、右4個(gè)方向可移動(dòng)，在四個(gè)角落上有2個(gè)方向可移動(dòng)，在其他位置上有3個(gè)方向可移動(dòng)。例如，假設(shè)一個(gè)3x3矩陣的初始狀態(tài)為：
8 0 3
2 1 4
7 6 5
目標(biāo)狀態(tài)為：
1 2 3
8 0 4
7 6 5
則一個(gè)合法的移動(dòng)路徑為：
8 0 3 8 1 3 8 1 3 0 1 3 1 0 3 1 2 3
2 1 4 => 2 0 4 => 0 2 4 => 8 2 4 => 8 2 4 => 8 0 4
7 6 5 7 6 5 7 6 5 7 6 5 7 6 5 7 6 5
另外，在所有可能的從初始狀態(tài)到目標(biāo)狀態(tài)的移動(dòng)路徑中，步數(shù)最少的路徑被稱為最短路徑；在上面的例子中，最短路徑為5。如果不存在從初試狀態(tài)到目標(biāo)狀態(tài)的任何路徑，則稱該組狀態(tài)無(wú)解。
請(qǐng)?jiān)O(shè)計(jì)有效的（細(xì)節(jié)請(qǐng)見評(píng)分規(guī)則）算法找到從八方塊的某初試狀態(tài)到某目標(biāo)狀態(tài)的所有可能路徑中的最短路徑，并用C/C++實(shí)現(xiàn)。
輸入數(shù)據(jù)：
程序需讀入已被命名為start.txt的初始狀態(tài)和已被命名為goal.txt的目標(biāo)狀態(tài)，這兩個(gè)文件都由9個(gè)數(shù)字組成（0表示空格，1-8表示8個(gè)數(shù)字方塊），每行3個(gè)數(shù)字，數(shù)字之間用空格隔開。
輸出數(shù)據(jù)：
如果輸入數(shù)據(jù)有解，輸出一個(gè)表示最短路徑的非負(fù)的整數(shù)；如果輸入數(shù)據(jù)無(wú)解，輸出-1。
自測(cè)用例：
如果輸入為：start.txt和goal.txt，則產(chǎn)生的輸出應(yīng)為：
5
又例，如果用
7 8 4
3 5 6
1 0 2
替換start.txt中的內(nèi)容，則產(chǎn)生的輸出應(yīng)為：
21
評(píng)分規(guī)則：
1）我們將首先使用和自測(cè)用例不同的10個(gè)start.txt以及相同的goal.txt，每個(gè)測(cè)試用例的運(yùn)行時(shí)間在一臺(tái)Intel Xeon 2.80GHz 4 CPU/6G 內(nèi)存的Linux機(jī)器上應(yīng)不超過(guò)10秒（內(nèi)存使用不限制），否則該用例不得分；
2）每個(gè)選手的總分（精確到小數(shù)點(diǎn)）=10秒鐘內(nèi)能產(chǎn)生正確結(jié)果的測(cè)試用例數(shù)量x10+（1/產(chǎn)生這些正確結(jié)果的測(cè)試用例的平均運(yùn)行毫秒)；
3）如果按此評(píng)分統(tǒng)計(jì)仍不能得出總決賽將決出的一、二、三等獎(jiǎng)共計(jì)九名獲獎(jiǎng)?wù)撸覀儗⑾仍O(shè)N=2，然后重復(fù)下述過(guò)程直至產(chǎn)生最高的9位得分：用隨機(jī)生成的另外10個(gè)有解的start.txt再做測(cè)試，并對(duì)這10*N個(gè)測(cè)試用例用2）中公式重新計(jì)算總分，N++。