k554 - 地雷很危險
題目描述
題目給定一個 N x M 的地圖，地圖上有些位置埋有兩種地雷：1號地雷和2號地雷。1號地雷影響其上下左右的格子，2號地雷影響其上下左右延伸至地圖邊界的格子。要求計算地圖上每個位置被地雷影響的風險值，風險值為該位置可能被炸到的地雷數量。
解題思路
本題可以使用模擬的方法解決。首先，建立一個與地圖大小相同的陣列 a，用於記錄每個位置的風險值。然後，遍歷地圖，對於每個地雷，根據其類型更新其影響範圍內格子的風險值。對於1號地雷，只需更新其上下左右格子的風險值。對於2號地雷，需要更新其上下左右延伸至地圖邊界的格子的風險值。最後，輸出陣列 a，即為每個位置的風險值。
複雜度分析
- 時間複雜度: O(NM(N+M))。遍歷地圖需要 O(N*M) 的時間，對於每個地雷，更新其影響範圍需要 O(N+M) 的時間（最壞情況下，2號地雷影響整個地圖）。
- 空間複雜度: O(N*M)。需要一個與地圖大小相同的陣列
a來記錄每個位置的風險值。
程式碼
#include <iostream>
using namespace std;
int a[105][105],n,m,x;
int main(){
cin >> n >> m;
for(int i=0;i<n;++i){
for(int j=0;j<m;++j){
cin >> x;
if(x==1){
a[i][j]++;
if(i+1<n)a[i+1][j]++;
if(i-1>=0)a[i-1][j]++;
if(j+1<m)a[i][j+1]++;
if(j-1>=0)a[i][j-1]++;
}
else if(x==2){
a[i][j]++;
for(int k=1;k<n;++k){
if(i+k<n)a[i+k][j]++;
if(i-k>=0)a[i-k][j]++;
}
for(int k=1;k<m;++k){
if(j+k<m)a[i][j+k]++;
if(j-k>=0)a[i][j-k]++;
}
}
}
}
for(int i=0;i<n;++i){
for(int j=0;j<m;++j){
cout << a[i][j] << " ";
}
cout << "\n";
}
}