作者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