PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [請益] 踩地雷的踩空處理

看板Prob_Solve (計算數學 Problem Solving)作者tkcn (小安)時間12年前 (2012/09/28 13:26)推噓2(2推 0噓 1→)

留言3則, 2人參與討論串3/3 (看更多)

※ 引述《EdisonX (閉上眼的魚)》之銘言： : (3) 關鍵在於 M$ 點到 0 的時候會自動再往外爆開，但這個怎麼做？ : 目前想法是，當遇到 0 的時候，開啟後，以 bfs 方向繼續往四個方向搜尋， : 搜尋到非零的時候就停下來， : void bfs(int x, int y) : { : if( map[x][y] == 0 && x>=0 && x<COL && y>=0 && y<ROW ) { : map[x][y]=9; : bfs(x+1,y); : bfs(x-1,y); : bfs(x,y+1); : bfs(x,y-1); : } : } 用 BFS 處理很好，不像 DFS 需要 function call，遇到真的很極端的 case 是有可能 stack overflow 的。不過你這裡 implement 的很明顯是 DFS， BFS 最大的特徵就是必須用到 Queue。 C 語法我不熟，所以用偏 Java 的語法大概寫一下: Queue q = new Queue(); q.offer(startX); q.offer(startY); while (!q.isEmpty()) { int currentX = q.poll(); int currentY = q.poll(); // handle current location for (int i=0; i<4; i++) { if (/* 已經踩過、超出範圍 */) continue; q.offer(currentX + dx[i]); q.offer(currentY + dy[i]); } } : 想試問在 (3) 之關鍵處是否合理？或是有其他方法做往外爆開？ : 另一個問題是，該格周圍有幾顆地雷，用事先算好方式會較佳嗎？ : 還是當 player 點開的時候再做處理會較佳？ : ( 是想問整體效能問題，直覺是先算好會較佳， : 但如果地圖很大的話，在初始化的時間就... ) 這差異對現在的電腦來說差異太小了。我的看法是，在你不確定優化所能帶來的影響之前，儘量保守一點，先採用簡單、安全的設計。等到你有了更多的證據，或著用 profiler 觀察過，確認執行的瓶頸確實在此，這時候再做優化也不遲。 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.114.78.231