a452: Bugs 公司
Tags :
Accepted rate : 11人/14人 ( 79% ) [非即時]
評分方式:
Tolerant

最近更新 : 2012-06-29 13:50

Content

 

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

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

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

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

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

Input

有多筆測試資料

第一行包含一個數字 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) 
Output
對於每筆測試資料輸出一個數字 x ,代表最多可以嵌入 x 張晶片。 
Sample Input #1
2
6 6 5
1 4
4 6
2 2
3 6
6 4
6 5 4
3 3
6 1
6 2
6 4
Sample Output #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
Hint :
Tags:
出處:
CEOI2002Bugs IntegratedInc. [管理者:
david942j (文旋)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」