回分類題庫
h084: F.轟炸任務
關鍵字: NPSC 2010 高中組決賽

測資點 : 2 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 13 Times / 13 Users | Submit : 18 Times / 14 Users | Accepted rate : 93%
題目加入時間 : 2012-11-04 02:24

Content: 简体中文

一個小小的通訊官,臨危受命要去指揮一個轟炸任務,對任何人來說都不好受吧。不巧地,你正好就是這個倒楣的通訊官。畢竟對於指揮轟炸一點經驗都沒有,只好從記憶中挖掘一些有用的資訊。

依稀記得昨天才被流彈打傷屁股而回家養傷的長官說過:「小子,戰場上也是講人道的!執行轟炸任務最討人厭的地方就是要避開那些學校和醫院,要是一不小心炸到哎呀真的是不得了阿,聯合國馬上就來找你麻煩;另外民用防空洞也不能炸太多次,如果你連續丟了兩顆炸彈在防空洞上,保證吃不完兜著走。」

副官已經把這次任務的目標建築都標示在地圖上。目標建築分為兩種,一種是碉堡,因為防禦工事做的比較完全,一般來說要投兩顆炸彈才能處理掉;另外一種是僅配備少量防禦工事的軍事陣地,只要一顆炸彈就足以將之摧毀。目標城市的地圖為棋盤狀,上方為北邊。

在指揮部,戰略攻擊機出發之際,你突然發現老長官訓練的駕駛員們有很大的問題。因為這些駕駛員不大會自行選擇路線,所以長官規定他們只能由北向南或是由西向東轟炸,中途不能轉彎,並且一旦選擇要轟炸這一列或是這一行則在這一列或這一行的每一格都要投下一顆炸彈。更令人頭痛的是,這些駕駛員們相當堅持一件事,就是絕對不對某一行或是某一列進行第二次轟炸。

這下可好了,你完全搞不懂老長官以前到底是如何指揮任務的,只對他這次因「重傷」而返家療傷之事又多知道了一些端倪。

身為一個程式設計師,請寫一支程式判斷自己是否能完成這次的任務。

Input:

第一行有一個數字T,代表總共有幾組測試資料。 

每組測試資料以三個整數 h,w, k 開頭,h 是地圖的高度,w 是地圖的寬度 (1 <= h,w <= 100),而 k 則代表地圖上總共有幾個需要注意到的建築 (0 <= k <= h×w)。

接下來 k 行每行依序給三個整數 yi, xi, ci 代表一個建築,yi 和xi 代表建築在地圖上的位置,其中 0 <= yi <= h-1,0 <= xi <= w-1;而 ci 則代表建築的種類,0 代表學校或醫院,1 代表碉堡,2 代表民用防空洞,3 代表一般軍事陣地。

Output:

對於每一組測試資料輸出一行 YES 或 NO,代表能否可以在不讓聯合國找上門的前提下擊破所有目標建築。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
2
3 4 4
0 2 0
1 1 0
2 0 0
2 3 0
3 4 4
0 2 0
1 1 0
2 0 0
2 3 1

Sample Output :

YES
NO

Hint :

Author :

NPSC 2010 高中組決賽 (管理員:sagit)

  Solve it!   Status Forum