作者EdisonX (闭上眼的鱼)
站内Prob_Solve
标题[请益] 踩地雷的踩空处理
时间Fri Sep 28 02:01:20 2012
这问题是额外进修，还没时间 application 出完整专案，
关於踩地雷相关演算法问题想请教与确认，
资料结构方式以 C code 大致示之。
(0) 假设在 30*30 地图 map[30][30] 上，随机放 50 颗地雷，想法大致如下。
#define ROW 30
#define COL 30
#define CNT 50
char map[ROW][COL]; /*global variable*/
int i, j, cnt;
memset(map, 0, sizeof(map)); /* initialize */
for(cnt=0; cnt<CNT; ){
i = rand() % ROW;
j = rand() % COL;
if(map[i][j]==0) map[i][j]=-1, ++cnt;
}
(1) 若 map[i][j] 本身是地雷，放 -1;
否则计算 map[i][j] 周围有几颗地雷，标示上去，
所以当 player 在点开 map[i][j] 的时候，不是临时才算的，
是事先算好调出来看的。
int dx[] = {-1,-1,-1, 0, 0, 1, 1, 1};
int dy[] = {-1, 0, 1,-1, 1,-1, 0, 1};
int k;
for(i=0; i<ROW; ++i){
for(j=0; j<COL; ++j){
if(map[i][j]==-1) continue;
for(k=0; k<8; ++k) { // 八个方位
int y = i+dy[k];
int x = j+dx[k];
if(x>=0 && x<COL && y>=0 && y<ROW && map[x][y]==-1)
++map[i][j];
}
}
}
(2) 点到-1 的话游戏结束；
点到 1~8 的时候只开启一格，并标示该格为 9 表示该格被开过。
(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);
}
}
想试问在 (3) 之关键处是否合理？或是有其他方法做 往外爆开？
另一个问题是，该格周围有几颗地雷，用事先算好方式会较佳吗？
还是当 player 点开的时候再做处理会较佳？
( 是想问整体效能问题，直觉是先算好会较佳，
但如果地图很大的话，在初始化的时间就... )
另外想额外问，有没有书籍或文章，在讲述，
怎麽以分析方式，
将 recursive 较有结构化方式、顺序拿掉？
手边有些程式很怕跑到 stack over flow
在此谢谢各位版友不吝赐教，小弟感激不尽。
--
「自从我学了 C# , 人都变聪明 , 考试都考一百分」
「自从我学了 VB , 皮肤都变好 , 人也变漂亮了 」
「自从我学了 Java , 明显变壮 , 个子也变高了 」
「自从我学了 C++ , 内分泌失调 , 头都秃了... 」
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 180.177.76.161
※ EdisonX:转录至看板 C_and_CPP 09/28 02:01
※ 编辑: EdisonX 来自: 180.177.76.161 (09/28 02:12)
1F：推 yauhh:递回分析的有效就是去看每一个呼叫,确定处理的范围有缩小. 09/28 08:27
2F：推 eight0:开到0时要递回八个方向 因为0表示周围都没有地雷 09/28 09:27
3F：→ EdisonX:真的是八个方向才对，谢谢楼上。 09/28 17:16
4F：→ tkcn:四个方向才对吧 09/28 17:40
5F：→ EdisonX:玩一下M$里面的踩地雷，它的作法比较像八个方向耶.. 09/28 18:11
6F：推 kiedveian:修改一下 Flood fill algorithm 应该可以…… 09/28 19:42
7F：→ kiedveian:啊，原来c++版有人回了 09/28 19:52
8F：→ tkcn:实际测试确实是八相邻，感谢。 09/28 23:42