c231 - 踩地雷

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算在一個地圖上，給定一些地雷的座標，需要最少使用多少枚誘導彈才能引爆所有地雷。地雷具有連鎖爆炸的特性，如果一個地雷的感測範圍內有其他地雷，則引爆一個地雷可以引爆其感測範圍內的所有地雷。

解題思路

這個問題可以透過貪婪演算法來解決。程式碼遍歷所有地雷，對於每個地雷，檢查其周圍 8 格內是否有其他地雷已經被引爆。如果沒有，則需要使用一枚新的誘導彈引爆該地雷，並將其周圍的已引爆地雷標記為已引爆。

程式使用一個 bomb 結構體來儲存地雷的編號、x 座標和 y 座標。ans 變數記錄所需誘導彈的數量，n 變數記錄已偵測到的地雷數量。程式首先讀取地圖大小和地雷數量，然後遍歷所有地雷，檢查其周圍是否有其他地雷。如果沒有，則增加 ans 的值，並將該地雷標記為已引爆。

複雜度分析

• 時間複雜度: O(n^2)，其中 n 是地雷的數量。因為對於每個地雷，都需要檢查其周圍 8 格內是否有其他地雷。
• 空間複雜度: O(n)，其中 n 是地雷的數量。因為需要儲存所有地雷的座標和編號。

程式碼

#include <iostream>//zj 的都過了，你們的測資很讚喔 
using namespace std;
int ans=0,n=0;
struct bomb{
	int no=0,x,y;
}a[10001];
int main(){
	int d;
	cin >> d >> d >> d;
	while(d--){
		cin >> a[n].x >> a[n].y;
		for(int i=0;i<n;i++)
			if(abs(a[i].x-a[n].x)<3&&abs(a[i].y-a[n].y)<3)
				a[n].no=ans;
		if(a[n].no==0){
			ans++;
			a[n].no=ans;
		}
		n++;
	}
	cout << ans << "\n";
}