PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[請益] 踩地雷的踩空處理

看板Prob_Solve (計算數學 Problem Solving)作者EdisonX (閉上眼的魚)時間12年前 (2012/09/28 02:01)推噓3(3推 0噓 5→)

留言8則, 5人參與討論串1/3 (看更多)

這問題是額外進修，還沒時間 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)