a452. Bugs 公司 - 高中生程式解題系統

內容

Bugs公司生產了一種 2 x 3 單位尺寸的高科技晶片，

晶片將被嵌入 n x m 單位尺寸的矩形晶圓內，但在生產晶圓原體的時候難免會有損壞的情況發生，

所以在經過嚴格的檢查之後，你在損壞的單位小方格內標上了黑色記號（見上圖）

而為了要保持晶片的良好運作，放置晶片的地方不能有損壞，晶片之間也不能互相重疊。

為了節省成本，公司希望將盡量多的晶片嵌入晶圓內，所以請你求出可能的最大晶片數量。

輸入說明

有多筆測試資料

第一行包含一個數字 T，代表有幾張晶圓需要你判斷。

每筆資料的：
第一行有三個數字，n, m, k，代表你的晶圓是 n x m 的，而其中有 k 格有損壞的情形。(1 <= n <= 150,1 <= m <= 10,k <= mn)

接下來有 k 行，每行有兩格數字 x,y 代表損壞位置的座標(1 <= x <= n, 1 <= y <= m)

輸出說明

對於每筆測試資料輸出一個數字 x ，代表最多可以嵌入 x 張晶片。

範例輸入 #1

範例輸出 #1

3
4

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (10%): 2.0s , <1K
公開測資點#1 (10%): 2.0s , <1M
公開測資點#2 (10%): 2.0s , <1K
公開測資點#3 (10%): 2.0s , <1K
公開測資點#4 (10%): 2.0s , <1M
公開測資點#5 (10%): 2.0s , <1M
公開測資點#6 (10%): 2.0s , <1M
公開測資點#7 (10%): 2.0s , <1M
公開測資點#8 (10%): 2.0s , <1K
公開測資點#9 (10%): 2.0s , <1K

提示：

標籤:

出處:

CEOI 2002 Bugs Integrated Inc. [管理者： david942j (文旋) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」