a452. Bugs 公司
標籤 :
通過比率 : 11人/15人 ( 73% ) [非即時]
評分方式:
Tolerant

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

內容

 

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
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
範例輸出 #1
3
4
測資資訊:
記憶體限制: 512 MB
提示 :
標籤:
出處:
CEOI2002Bugs IntegratedInc. [管理者: david942j (文旋) ]

本題狀況 本題討論 排行

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