f928 - 連環炸彈.................Boom！
題目描述
題目描述了一個炸彈連環爆炸的過程。給定一串炸彈的類型，以及一個起始引爆點，模擬炸彈爆炸的過程，並輸出最終炸彈的狀態。炸彈類型分為啞炮(1)、左右炮(2)和怪怪炮(k >= 3)，它們的爆炸範圍不同。
解題思路
本題可以使用深度優先搜尋 (DFS) 來模擬炸彈爆炸的連環反應。從起始炸彈開始，根據其類型引爆周圍的炸彈，並重複此過程直到沒有新的炸彈可以引爆。在引爆炸彈時，將其狀態設為 0。需要注意邊界條件，避免訪問陣列越界。
複雜度分析
- 時間複雜度: O(N^2)，在最壞情況下，每個炸彈都可能引爆其他炸彈，導致需要遍歷整個陣列多次。
- 空間複雜度: O(N)，主要用於遞迴調用的堆疊空間，在最壞情況下，遞迴深度可能達到 N。
程式碼
#include <iostream>
using namespace std;
int n,a[1005],s;
void dfs(int it){
if(it<0||it>=n||a[it]==0)return;
int t=a[it];
a[it]=0;
if(t==2){
dfs(it+1);
dfs(it-1);
}
else if(t>2){
dfs(it+2*t);
dfs(it-2*t);
dfs(it+t);
dfs(it-t);
}
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> n;
for(int i=0;i<n;++i){
cin >> a[i];
}
cin >> s;
dfs(s);
for(int i=0;i<n;++i){
cout << a[i] << " ";
}
}