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