c165 - NOIP2015 2.扫雷游戏
題目描述
題目要求模擬掃雷遊戲，給定一個 n x m 的雷區地雷分布，計算每個非地雷格周圍的地雷數量，並輸出結果。地雷用 '*' 表示，非地雷格用周圍地雷的數量表示。
解題思路
本題的解題思路是模擬掃雷遊戲的規則。首先，建立一個與輸入雷區相同大小的二維陣列 ans，用於儲存每個格子的地雷數量。遍歷輸入雷區，如果遇到地雷，則將其周圍八個格子的地雷數量加一。最後，遍歷 ans 陣列，如果格子是地雷，則輸出 '*'，否則輸出該格子的地雷數量。
複雜度分析
- 時間複雜度: O(n*m)
- 空間複雜度: O(n*m)
程式碼
#include <iostream>
using namespace std;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
int a,b;
while(cin >> a >> b){
char n;
int ans[a][b];
for(int i=0;i<a;i++){
for(int j=0;j<b;j++){
ans[i][j]=0;
}
}
for(int i=0;i<a;i++){
for(int j=0;j<b;j++){
cin >> n;
if(n=='*'){
for(int ii=-1;ii<=1;ii++)
for(int jj=-1;jj<=1;jj++)
if(i+ii>=0&&i+ii<a&&j+jj>=0&&j+jj<b)
ans[i+ii][j+jj]++;
ans[i][j]-=10;
}
}
}
for(int i=0;i<a;i++){
for(int j=0;j<b;j++){
if(ans[i][j]>=0)
cout << ans[i][j];
else
cout << "*";
}
cout << "\n";
}
}
}