1420 . 地雷區 (Mine)
TopCoder
Description
國家防衛隊的防衛系統發現，敵國一夕之間在兩國交界區域佈下許多地雷，這種地雷的特性是周圍均有感測裝置，只要觸發感測裝置就會引發地雷爆炸，而如果感測裝置上也有其他地雷的感測裝置，就會引發連鎖感應而產生連環爆炸。國家防衛隊已偵測到地雷的座標位置，並準備使用誘導彈引爆所有的地雷，你的任務就是根據地雷的座標，並善加利用地雷的連鎖感應機制，讓國家防衛隊所需使用的誘導彈數量越少越好。
若以$ a \times b $表示地圖大小，並以座標$（1, 1）$表示左上角位置。下圖即為一個 $8 \times 10 $的地圖，其中$ M $標示地雷位置，其周圍灰色區域為感測裝置，只要誘導彈命中地雷$（3, 3）$或$（5, 5）$或其周圍任一感測裝置，就可以一次引爆這兩個地雷，但地雷$（2, 9）$及$（5, 10）$各需一顆誘導彈加以引爆，所以一共只需要發射 $3$ 顆誘導彈就可以引爆四個地雷。
Input Format
第一列為三個正整數，以一個空白為間隔，其中前兩個正整數$a, b$代表地圖的大小，第三個正整數$c \leq 50000$代表地雷數量。接下來有$c$列，每一列有兩個以空白為間隔的的正整數$row, col$代表地雷的座標，座標不重複，$1\leq row, col \leq 10000$。
Output Format
能成功引爆所有地雷所需最少誘導彈數量（一個正整數）。
Sample Input 1
10 10 2
1 1
10 10
1 1
10 10
Sample Output 1
2
Sample Input 2
10 6 3
2 2
3 3
4 5
2 2
3 3
4 5
Sample Output 2
1
Hints
Problem Source
臺北市105學年度高級中學資訊學科能力競賽程式設計試題第二題
Set by Yihda Yol
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0~3 | 25 |
| 2 | 0~7 | 25 |
| 3 | 0~11 | 25 |
| 4 | 0~15 | 25 |