f149 - 3. 炸彈偵測器 (Detector)
題目描述
題目給定一個二維地圖，其中包含 1 (安全地帶)、5 (炸彈) 和 0 (障礙物)。炸彈會影響周圍八個格子（包含自己），將周圍格子的危險度加 1。如果一個炸彈周圍的危險度大於 1，則該炸彈會被移除（變成 0）。接著，如果安全地帶周圍有炸彈，則該安全地帶也會被移除（變成 0）。最後，計算移除的炸彈數量和剩餘的安全地帶數量。
解題思路
本題主要使用模擬的方法來解決。首先，遍歷地圖，找出所有炸彈的位置，並計算每個格子受炸彈影響的危險度。然後，再次遍歷地圖，移除危險度大於 1 的炸彈。接著，遍歷地圖，如果安全地帶周圍有炸彈，則移除該安全地帶。最後，統計移除的炸彈數量和剩餘的安全地帶數量。
複雜度分析
- 時間複雜度: O(x * y)，其中 x 和 y 分別是地圖的行數和列數。需要遍歷地圖三次。
- 空間複雜度: O(x * y)，主要用於儲存地圖和危險度陣列。
程式碼
#include <stdio.h>
int sum[17][17],x,y,map[16][16],no(0),ya(0),i(0),j(0),ii,jj;
int main(){
scanf("%d%d",&x,&y);
for(i=0;i<x;++i)
for(j=0;j<y;++j){
scanf("%d",&map[i][j]);
if(map[i][j]==5)
for(ii=-1;ii<=1;++ii)
for(jj=-1;jj<=1;++jj)
if(ii+i>=0&&jj+j>=0)
++sum[ii+i][jj+j];
}
for(i=0;i<x;++i)
for(j=0;j<y;++j)
if(map[i][j]==5&&sum[i][j]>1)
map[i][j]=0;
for(i=0;i<x;++i)
for(j=0;j<y;++j){
if(map[i][j]==1)
for(ii=-1;ii<=1;++ii)
for(jj=-1;jj<=1;++jj)
if(ii+i>=0&&jj+j>=0&&map[ii+i][jj+j]==5){
map[i][j]=0;
++ya;
ii=2;
break;
}
if(map[i][j]==1)
++no;
}
printf("%d %d",ya,no);
}