[Java] UVa 11044 Searching for Nessy

題目連結

題意:
看來是跟尼斯湖水怪有關的題材，重點從第三段開始，Given a grid of...
測資提供一個n * m的網格，要在網格內放類似監視器的東西(大概吧)

每個監視器可以涵蓋一個九宮格的範圍
求最少需要多少監視器(不含最外圈，即示意圖藍色部分)

解法:
看起來是很麻煩的空間題目，右邊只是故意放得很複雜
為了符合最低需求，只要設想藍色範圍需要多少監視器即可

對於網格 m 或 n 而言，每個監視器都佔相同3格範圍
所以可以m n分別以3為單位區分來算
假設邊長6 (m n皆 ≧ 6)，監視器要涵蓋 4，最少需要2台(3*2 = 6需 ≧ 4)
邊長7時涵蓋5，需要2台
邊長8時涵蓋6，需要2台
邊長9時涵蓋7，需要3台
...

可以發現所需監視器數恰等於邊長除以3
結果為column * row

程式(Java):

	import java.util.*;
	public class Main {
	public static void main(String args[]) {
	Scanner sc = new Scanner(System.in);
	int t = sc.nextInt();
	while (t-- > 0) {
	int n = sc.nextInt();
	int m = sc.nextInt();
	System.out.println((m/3) * (n/3));
	}
	}
	}

view raw UVa11044.java hosted with ❤ by GitHub