n700 - 蝸牛的踩地雷攻略 3 (點方塊)
題目描述
題目要求模擬踩地雷遊戲，給定地雷分佈和起始點，輸出點擊起始點後的地圖狀態。地圖上 # 表示未翻開的格子，* 表示地雷，數字表示周圍地雷數量，_ 表示該格子及其周圍均無地雷。
解題思路
本題的核心是使用深度優先搜尋 (DFS) 演算法來模擬點擊空格後的連鎖反應。首先，計算每個格子周圍的地雷數量，並儲存在 ct 陣列中。然後，從起始點開始進行 DFS，如果當前格子沒有地雷，且周圍也沒有地雷，則將其標記為已翻開 (open 陣列)，並遞迴地翻開其周圍的格子。如果當前格子有地雷，則停止 DFS。最後，根據 open 和 ct 陣列的狀態，輸出地圖。
複雜度分析
- 時間複雜度: O(n*m)，其中 n 是地圖的高度，m 是地圖的寬度。因為 DFS 最多會遍歷所有格子一次。
- 空間複雜度: O(nm)，主要用於儲存
ct和open陣列，以及 DFS 的遞迴堆疊空間。在最壞情況下，遞迴深度可能達到 nm。
程式碼
#include <iostream>
using namespace std;
int ct[31][31];
bool open[31][31];
void dfs(int x,int y,int n,int m){
if(x<0 || x>=n || y<0 || y>=m || open[x][y]){
return;
}
open[x][y]=true;
if(ct[x][y]>0){
return;
}
for(int i=-1;i<=1;i++){
for(int j=-1;j<=1;j++){
dfs(x+i,y+j,n,m);
}
}
}
int main(){
int n,m,x,y;
cin >> n >> m >> x >> y;
string s[n];
for(int i=0;i<n;i++){
cin >> s[i];
for(int j=0;j<m;j++){
if(s[i][j]=='*'){
for(int ii=-1;ii<=1;ii++){
for(int jj=-1;jj<=1;jj++){
if(i+ii>=0 && i+ii<n && j+jj>=0 && j+jj<m){
ct[i+ii][j+jj]++;
}
}
}
}
}
}
--x;--y;
dfs(x,y,n,m);
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(open[i][j]){
if(ct[i][j]){
cout << ct[i][j];
}
else{
cout << "_";
}
}else {
cout << "#";
}
}
cout << '\n';
}
}