d039 - 11044 - Searching for Nessy

🔗 前往 ZeroJudge 原題

題目描述

題目描述了在尼斯湖中尋找尼斯湖水怪的問題。給定一個 n x m 的格子，需要放置聲納來監控整個湖面。聲納可以監控自身及其相鄰的格子。邊緣的格子不需要監控。目標是找到最少需要放置多少個聲納才能覆蓋整個湖面（不包括邊緣）。

解題思路

由於聲納的監控範圍是自身和相鄰的格子，我們可以將聲納放置在棋盤格的形式上，以最大化覆蓋範圍。具體來說，我們可以在每隔兩格放置一個聲納。這樣，每個聲納可以覆蓋一個 3x3 的區域（考慮到邊緣不需監控，實際覆蓋的區域會小於 3x3）。因此，所需的聲納數量可以通過將 n 和 m 除以 3 並取整來計算。

複雜度分析

• 時間複雜度: O(1)
• 空間複雜度: O(1)

程式碼

#include <stdio.h>
int main(){
	int a,b;
	scanf("%d",&a);
	while(scanf("%d%d",&a,&b)!=EOF)
		printf("%d\n",(a/3)*(b/3));
}