c231. 踩地雷
標籤 : TIOJ 1420
通過比率 : 174人/251人 ( 69% ) [非即時]
評分方式:
Tolerant

最近更新 : 2017-08-27 16:05

內容

國家防衛隊的防衛系統發現,敵國一夕之間在兩國交界區域佈下許多地雷,這種地雷
的特性是周圍8格均有感測裝置,只要觸發感測裝置就會引發地雷爆炸,而如果感測裝置上也
有其他地雷的感測裝置,就會引發連鎖感應而產生連環爆炸。
國家防衛隊已偵測到地雷的座標位置,並準備使用誘導彈引爆所有的地雷,你的任務
就是根據地雷的座標,並善加利用地雷的連鎖感應機制,讓國家防衛隊所需使用的誘導彈
數量越少越好。

輸入說明

第一列為三個正整數,以一個空白為間隔,其中前兩個正整數 a, b 代表地圖的大小,
第三個正整數 c 代表地雷數量。接下來有 c 列,每一列有兩個以空白為間隔的正整數row,
col 代表地雷的座標,座標不重複,1 ≤ row, col ≤ 10,000。

輸出說明

能成功引爆所有地雷所需最少誘導彈數量

範例輸入 #1
10 10 2
1 1
10 10
範例輸出 #1
2
測資資訊:
記憶體限制: 400 MB
提示 :
標籤:
TIOJ 1420
出處:
2016台北市資訊學科能力複賽 [管理者: k034006 (Sine Wu) ]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
20737 yes51851823@ ... (wseds) c231
可無視地圖大小
1571 2020-02-27 19:37