c231: 踩地雷
標籤 : TIOJ 1420
通過比率 : 84% (26 人 / 31 人 ) (非即時)
評分方式:
Tolerant

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

內容

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

輸入說明

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

輸出說明

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

範例輸入
10 10 2
1 1
10 10
範例輸出
2
測資資訊:
記憶體限制: 400 MB
不公開 測資點#0 (25%): 1.0s , <1K
不公開 測資點#1 (25%): 1.0s , <1K
不公開 測資點#2 (25%): 1.0s , <1M
不公開 測資點#3 (25%): 1.0s , <1K
提示 :
標籤:
TIOJ 1420
出處:
2016台北市資訊學科能力複賽 [編輯:
k034006 (Sine Wu)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」