作者tkcn (小安)
看板Prob_Solve
標題Re: [請益] 踩地雷的踩空處理
時間Fri Sep 28 13:26:30 2012
※ 引述《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
1F：推 EdisonX:感謝您的建議,原來之前我一直把 dfs 當 bfs.. 09/28 17:28
2F：推 Arton0306:或者也可以用stack 反正不需要bfs的特性 09/29 01:19
3F：→ Arton0306:好處是vector可能比queue快一點 空間省一點 09/29 01:21