二輪day2 snake解題報告_第1頁
二輪day2 snake解題報告_第2頁
二輪day2 snake解題報告_第3頁
全文預覽已結束

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領

文檔簡介

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

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論