回分類題庫
h080: B.薑餅部落的浩劫
關鍵字: NPSC 2010 高中組決賽

測資點 : 2 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 9 Times / 8 Users | Submit : 103 Times / 19 Users | Accepted rate : 42%
題目加入時間 : 2012-11-04 02:23

Content: 简体中文

薑餅部落在順利地克服海水威脅後人口開始急遽上升,造成居住島嶼不堪負荷、人滿為患,薑餅人們甚至為了地盤不惜對同胞拳腳相向,長老幾經思慮後決定建造一座巨大的方形高塔已收容那些無家可歸的薑餅人。

新建成的高塔呈完美的長方體,遠望非常雄偉,近看便會發現是由許許多多個相同大小的正方體小房間所組成,每個小房間都住有一個薑餅人,它們似乎又解決了一次難題。可惜,原本在天空中遊蕩的飛行麵條怪物 Spaghetti 聞到了薑餅人們散發的香味,打算帶走它們作為自己的小點心!!

Spaghetti 不斷地把麵條一般細長的手直直伸入塔內,每次都把住在同排的薑餅人們全數抓走。最後,Spaghetti 已騰不出手來掠奪更多的薑餅人,便帶著它們飛得遠遠地準備慢慢享用。長老立即下令撤出高塔,但這群可憐的薑餅人們已嚇得不敢動作,請你幫助長老計算塔內剩餘的薑餅人總數。

Input:

測資包含多組測試資料,第一列有一個整數 T 表示接下來有幾組測試資料。

每組測試資料其第一列有三個整數 N, M, H,代表高塔的長、寬、高,單位為 1 個小房間的邊長。第二列有一個整數 S 表示 Spaghetti 將手伸入塔內的次數。其後有 S 列輸入,每列輸入有三個整數 (xi, yi, zi),其中必恰有一者為 0 表示 Spaghetti 手伸入的方向,其餘兩者表示 Spaghetti 手伸入的位置。舉例來說,(1, 1, 0) 代表 Spaghetti 從第 1 行第 1 列將手由上往下伸入,並且帶走該行該列所有樓層的薑餅人。你可以假設 Spaghetti 不會對相同位置從相同方向把手伸入超過一次。(1 <= N,M,H <= 50000, 1 <= S <= 5000, 0 <= xi <= N, 0 <= yi <= M, 0 <= zi <= H)。

Output:

對每筆測試資料輸出塔內剩餘的薑餅人總數。

Sample Input:help

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

Sample Output :

1
6

Hint :

Author :

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

  Solve it!   Status Forum