e568 - 11639 - Guard the Land
題目描述
題目描述了農夫 Latif 的土地，以及兩名守衛各自守護的矩形區域。要求計算強安全區（兩個守衛都守護的區域）、弱安全區（只有一個守衛守護的區域）和非安全區（沒有守衛守護的區域）的面積。
解題思路
此題的核心思路是使用一個陣列來模擬土地上的每個點，並標記每個點被守衛守護的次數。
- 建立一個大小為 100x100 的陣列
ans，用於記錄每個點被守護的次數。由於陣列索引只能是非負整數，因此將座標 (x, y) 映射到一個一維索引x + y * 100。 - 對於每個守衛的矩形區域，遍歷該區域內的每個點，並將
ans陣列中對應索引的值加 1。 - 遍歷
ans陣列，統計被守護 2 次（強安全區）、1 次（弱安全區）和 0 次（非安全區）的點的數量。 - 計算每個區域的面積，並輸出結果。
複雜度分析
- 時間複雜度: O(n * w * h)，其中 n 是夜晚的數量，w 和 h 分別是土地的寬度和高度 (100)。由於需要遍歷兩個矩形區域，因此時間複雜度為 O(n * 100 * 100)。
- 空間複雜度: O(w * h)，其中 w 和 h 分別是土地的寬度和高度 (100)。空間複雜度主要來自於
ans陣列，其大小為 100 * 100。
程式碼
#include <iostream>
using namespace std;
int main(){
int n;
cin >> n;
for(int ca=1;ca<=n;++ca){
int a[8],ans[10001]={0},x=0,y=0,z=0;
for(int i=0;i<8;++i){
cin >> a[i];
}
for(int i=a[0];i<a[2];++i){
for(int j=a[1];j<a[3];++j){
++ans[i+j*100];
}
}
for(int i=a[4];i<a[6];++i){
for(int j=a[5];j<a[7];++j){
++ans[i+j*100];
}
}
for(int i=0;i<10000;++i){
if(ans[i]==2){
++x;
}
else if(ans[i]==1){
++y;
}
else{
++z;
}
}
cout << "Night " << ca << ": " << x << " " << y << " " << z << "\n";
}
}