[Java] UVa 10703 Free spots

題目連結

題意:
大意是給定一個長方形的長與寬
還有若干個小長方形(座標)
求原長方形內未包含在小長方形的面積大小

每組測資由3個數字為一行開頭
分別為W, H, N，W, H代表長方形的寬, 高
N為 後面還有 N 行測資，代表 N 個小長方形
每行分別有4個數字，為小長方形的對角線座標

舉例而言，有一組測資為:

4 3 1
1 2 4 3

表示有個4 * 3長方形
與一個對角座標為(1, 2), (4, 3)的小長方形(下圖紅框處為對角座標)
則剩餘面積為 4

解法:
根據大長方形的寬, 高建陣列
走訪每個小長方形佔到的面積做註記(如圖上綠色部分)
最後統計陣列內還沒註記的總和即可

要注意小長方形測資並沒有保證前者的座標會小於後者
也就是不一定為左下-右上的座標對
如上圖，也可能是(1, 3), (4, 2)(指的是相同小長方形)

不過，不論是何者，我們的目標是該綠色部分都要註記即可
迴圈部分可以這樣寫:
for (int i = Math.min(a1, b1); i <= Math.max(a1, b1); i++)
for (int j = Math.min(a2, b2); j <= Math.max(a2, b2); j++)

(a1, a2) (b1, b2)分別為2個對角座標測資

程式(Java):

	import java.util.*;
	public class Main {
	public static void main(String args[]) {
	Scanner sc = new Scanner(System.in);
	while (sc.hasNext()) {
	int W = sc.nextInt();
	int H = sc.nextInt();
	boolean field[][] = new boolean[W+1][H+1];
	int N = sc.nextInt();
	if (W == 0 && H == 0 && N == 0)
	break;
	while (N-- > 0) {
	int a1 = sc.nextInt();
	int a2 = sc.nextInt();
	int b1 = sc.nextInt();
	int b2 = sc.nextInt();
	for (int i = Math.min(a1, b1); i <= Math.max(a1, b1); i++) {
	for (int j = Math.min(a2, b2); j <= Math.max(a2, b2); j++)
	field[i][j] = true;
	}
	}
	int count = 0;
	for (int i = 1; i <= W; i++)
	for (int j = 1; j <= H; j++)
	if (!field[i][j])
	count++;
	if (count == 0)
	System.out.println("There is no empty spots.");
	else if (count == 1)
	System.out.println("There is one empty spot.");
	else
	System.out.println("There are " + count +" empty spots.");
	}
	}
	}

view raw UVa10703.java hosted with ❤ by GitHub