※ [本文轉錄自 Prob_Solve 看板 #1GP9Hqvk ]

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

※ 發信站: 批踢踢實業坊(ptt.cc)
※ 轉錄者: EdisonX (180.177.76.161), 時間: 09/28/2012 02:01:55
※ 編輯: EdisonX 來自: 180.177.76.161 (09/28 02:13)