e838 - P5. 炸彈超人(Bombs)
題目描述
題目描述了一個炸彈超人的遊戲地圖，地圖上有一些炸彈。當炸彈爆炸時，會以十字形狀向四周擴散，直到地圖邊界。題目要求輸出炸彈爆炸後的遊戲地圖，被炸彈影響的格子標記為 *，未受影響的格子標記為 0。
解題思路
這個問題可以使用模擬的方法來解決。首先，讀取地圖的輸入，並將炸彈的位置記錄下來。然後，對於每個炸彈，遍歷整個地圖，將炸彈爆炸範圍內的格子標記為 *。具體來說，對於每個炸彈的位置 (i, j)，將第 i 行和第 j 列的所有格子標記為 *。最後，輸出更新後的遊戲地圖。
複雜度分析
- 時間複雜度: O(n^3)，其中 n 是地圖的邊長。因為需要遍歷每個炸彈，並且對於每個炸彈，需要遍歷整個地圖的每一行和每一列。
- 空間複雜度: O(n^2)，因為需要使用一個 n x n 的二維陣列來儲存地圖的狀態。
程式碼
#include <iostream>
using namespace std;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
int n;
char a;
while(cin >> n){
bool b[n][n];
bool ans[n][n];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
b[i][j]=0;
ans[i][j]=0;
cin >> a;
if(a=='*'){
b[i][j]=1;
}
}
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(b[i][j]==1){
for(int ii=0;ii<n;ii++){
ans[i][ii]=1;
ans[ii][j]=1;
}
}
}
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(ans[i][j]==1){
cout << '*';
}
else{
cout << '0';
}
}
cout << "\n";
}
}
}