1420 . 地雷區 (Mine)

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

icube
baluteshih 好強 <(_ _)>

User's AC Ratio

80.4% (152/189)

Submission's AC Ratio

29.4% (269/914)

Tags

北市賽 2016-北市賽

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

Sample Output 1

2

Sample Input 2

10 6 3
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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 262144 1 2 3 4
1 1000 524288 262144 1 2 3 4
2 1000 524288 262144 1 2 3 4
3 1000 524288 262144 1 2 3 4
4 1000 524288 262144 2 3 4
5 1000 524288 262144 2 3 4
6 1000 524288 262144 2 3 4
7 1000 524288 262144 2 3 4
8 1000 524288 262144 3 4
9 1000 524288 262144 3 4
10 1000 524288 262144 3 4
11 1000 524288 262144 3 4
12 1000 524288 262144 4
13 1000 524288 262144 4
14 1000 524288 262144 4
15 1000 524288 262144 4
Submit
Back to Top