1468 . 晶片放置問題
TopCoder
Tags
Description
你是一名強大的工程師，
最近你的公司生產了一種 2 x 3 單位尺寸的高科技晶片，
晶片將被嵌入 n x m 單位尺寸的矩形晶圓內，但在生產晶圓原體的時候難免會有損壞的情況發生，
所以在經過嚴格的檢查之後，你在損壞的單位小方格內標上了黑色記號（見上圖）
而為了要保持晶片的良好運作，放置晶片的地方不能有損壞，晶片之間也不能互相重疊。
為了節省成本，公司希望將盡量多的晶片嵌入晶圓內，所以請你求出可能的最大晶片數量。
Input Format
本題有多筆測試資料：
第一行包含一個數字 T，代表有幾張晶圓需要你判斷。
每筆資料的：
第一行有三個數字，n, m, k，代表你的晶圓是 n x m 的，而其中有 k 格有損壞的情形。(1 <= n <= 500,1 <= m <= 10,k <= mn)
接下來有 k 行，每行有兩格數字 x,y 代表損壞位置的座標(1 <= x <= n, 1 <= y <= m)
Output Format
對於每筆測試資料輸出一個數字 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
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
4
Hints
Problem Source
原TIOJ1468 / 建中校內培訓第四次模擬考試。
Problem Setter：hallogameboy、peter50216
(Adapt From：CEOI 2002)
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 9 |
| 2 | 1 | 9 |
| 3 | 2 | 9 |
| 4 | 3 | 9 |
| 5 | 4 | 9 |
| 6 | 5 | 9 |
| 7 | 6 | 9 |
| 8 | 7 | 9 |
| 9 | 8 | 9 |
| 10 | 9 | 9 |
| 11 | 10 | 10 |