二輪day2 snake解題報(bào)告

其實(shí)就是給定一幅地圖，有，移動(dòng)時(shí)間根據(jù)位置不同而不同（但這題難度不大，主要選手對(duì)BFS的運(yùn)用能力，對(duì)時(shí)間、空間的優(yōu)BFS，首先要設(shè)計(jì)好狀態(tài)。對(duì)于此題，顯然，蛇的位置要的，蛇的形態(tài)也是要的。由于不是單一位置作為目標(biāo)，而是有多個(gè)食物，所以食物的存在情況也是要的。跟一般的BFS題目相比，此題還有一個(gè)特別的條件，就是移動(dòng)的時(shí)間代價(jià)不一定是1。單純這樣想，似乎BFS就不可做了。但是，問題可以稍時(shí)間，這樣的話，可以使得狀態(tài)轉(zhuǎn)移的代價(jià)仍為1，就可以使用BFS了。這樣，需要再下等候時(shí)間這個(gè)信息。整條蛇的位置也就確定了。蛇頭的位置有151544344334、5、6、74(3233343514402416間可能有8種，所以總狀態(tài)數(shù)是225?1440?16?8 這里有一個(gè)細(xì)節(jié)問題，就是蛇長(zhǎng)為8的形態(tài)不需要統(tǒng)計(jì)，因?yàn)槟潜厝豢梢灾?，蛇的形態(tài)，只要保證不自交即可。是否自交，也只跟原始形態(tài)以及方向有關(guān)，跟位置無(wú)關(guān)，所以，主過程中完全不必要處理蛇的形態(tài)。并且，在不同位置不同的食物狀態(tài)、等候時(shí)間，同一種形態(tài)變換結(jié)果是一樣的，可以預(yù)先把所有蛇的形態(tài)變換預(yù)處理出來(lái)，并在主過程中以標(biāo)號(hào)代替狀態(tài)壓縮，節(jié)省時(shí)間和空間。在預(yù)處理過程中，同樣使用BFS。不同的形態(tài)在隊(duì)列中出現(xiàn)的位置是如何轉(zhuǎn)移的。對(duì)于1440種形態(tài)（根據(jù)程序計(jì)算的結(jié)果，實(shí)質(zhì)只有種），每種形態(tài)記錄下向4個(gè)方向和向4個(gè)方向進(jìn)食后的狀態(tài)編號(hào)即首先要準(zhǔn)確計(jì)算，總狀態(tài)數(shù)應(yīng)該是225?1200?16?8= 約是35M。35M的狀態(tài)總數(shù)，但是隊(duì)列需要記錄的信息眾多，需要很謹(jǐn)慎地使用空間，才能避免MLE。蛇頭的兩個(gè)坐標(biāo)各需1個(gè)字節(jié)，形態(tài)記21個(gè)字節(jié)，狀態(tài)轉(zhuǎn)移的前驅(qū)需410350MB內(nèi)存，加上判重需要35MB400MB的內(nèi)存使用了。如果寫程序的時(shí)候一時(shí)爽，全部intPascalrecodeMLE。所以必須小 程序的做法，大概就是，把前6個(gè)字節(jié)的信息用一個(gè)二進(jìn)制壓縮掉，剩下27位，可以用4個(gè)字節(jié)起來(lái)。1個(gè)字節(jié)8個(gè)二進(jìn)制位，只用來(lái)一個(gè)bool有點(diǎn)浪費(fèi)，就用位運(yùn)算拆開8個(gè)使用好了，通過以上，可以把總內(nèi)存控制在300MB左右其實(shí)有個(gè)小，可以發(fā)現(xiàn)實(shí)際的狀態(tài)數(shù)是沒有那么多的，那么……存不夠用的時(shí)候把隊(duì)列開小一點(diǎn)通常也是可行的。本來(lái)打算卡空間的，結(jié)果發(fā)現(xiàn)壓縮也不是能節(jié)省特別多的內(nèi)存，于是就沒有特意卡了。POJ1324，不過經(jīng)過