二輪day2 snake解題報告

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