1420 . 地雷區 (Mine)

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

icube
baluteshih 好強 <(_ _)>

User's AC Ratio

79.7% (153/192)

Submission's AC Ratio

29.3% (270/921)

Tags

北市賽 2016-北市賽

Description

　　國家防衛隊的防衛系統發現，敵國一夕之間在兩國交界區域佈下許多地雷，這種地雷的特性是周圍均有感測裝置，只要觸發感測裝置就會引發地雷爆炸，而如果感測裝置上也有其他地雷的感測裝置，就會引發連鎖感應而產生連環爆炸。國家防衛隊已偵測到地雷的座標位置，並準備使用誘導彈引爆所有的地雷，你的任務就是根據地雷的座標，並善加利用地雷的連鎖感應機制，讓國家防衛隊所需使用的誘導彈數量越少越好。
　　若以a×b表示地圖大小，並以座標（1,1）表示左上角位置。下圖即為一個 8×10的地圖，其中M標示地雷位置，其周圍灰色區域為感測裝置，只要誘導彈命中地雷（3,3）或（5,5）或其周圍任一感測裝置，就可以一次引爆這兩個地雷，但地雷（2,9）及（5,10）各需一顆誘導彈加以引爆，所以一共只需要發射 3 顆誘導彈就可以引爆四個地雷。
​

Input Format

第一列為三個正整數，以一個空白為間隔，其中前兩個正整數a,b代表地圖的大小，第三個正整數c≤50000代表地雷數量。接下來有c列，每一列有兩個以空白為間隔的的正整數row,col代表地雷的座標，座標不重複，1≤row,col≤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