User's AC Ratio

72.1% (49/68)

Submission's AC Ratio

33.7% (117/347)

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

For Testdata: 0 ~ 3, Score: 25
For Testdata: 0 ~ 7, Score: 25
For Testdata: 0 ~ 11, Score: 25
For Testdata: 0 ~ 15, Score: 25
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 524288 262144
1 1000 524288 262144
2 1000 524288 262144
3 1000 524288 262144
4 1000 524288 262144
5 1000 524288 262144
6 1000 524288 262144
7 1000 524288 262144
8 1000 524288 262144
9 1000 524288 262144
10 1000 524288 262144
11 1000 524288 262144
12 1000 524288 262144
13 1000 524288 262144
14 1000 524288 262144
15 1000 524288 262144