TopCoder

User's AC Ratio

76.5% (65/85)

Submission's AC Ratio

32.8% (134/409)

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

#輸入範例2
10 6 3
2 2
3 3
4 5

Sample Output

#輸出範例1
2

#輸出範例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 (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