1519 . [APIO '12] 苦無問題
TopCoder
Description
苦無 (Kunai) 是一個刀子形狀的尖銳武器，忍者會對他們的敵人投擲苦無。
現在有 N 名忍者在 H 列 W 行的方陣中，每名忍者在格子的正中央，並且一個格子不會有兩名以上的忍者。每名忍者都有一把苦無，並且面向上、下、左、右四個方向中的其中一個方向。在時間點 0 時，每名忍者朝他們面向的方向投擲出苦無。
每把苦無以速度 1 直線前進，如果有不止一把苦無在同一時間飛到同一地點，它們會破撞並且消失。我們可以忽略苦無的大小。另外，由於忍者可以快速移動，所以他們不會被苦無擊中。每把苦無會以等速直線飛行，除非和另外的苦無碰撞。
在下圖中，箭頭代表苦無，箭頭方向代表苦無飛行的方向，在這些圖中，所有粗體的箭頭都會發生碰撞。
而在下列圖中，粗箭頭並不會和另一個粗箭頭相撞。第二和第三張圖中，細箭頭會和一個粗箭頭相撞。因為相撞的箭頭會消失，因此這兩張圖中各有一個粗箭頭不會發生碰撞而會持續飛行。
請計算足夠長的時間後，在 W×H 方格中有多少方格會有苦無飛過。
Input Format
第一行輸入兩個用空白隔開的整數 W 和 H，代表方陣的大小。
第二行輸入一個整數 N，代表忍者的數量。
接下來的 N 行中的第 i 行 ($1\leq i\leq N$) 有三個用空白隔開的整數$X_i, Y_i, D_i$，代表忍
者 i 位在第$X_i$行（從左而右）和第$Y_i$列（從上而下）的格子；$D_i$代表忍者$i$面對的方向。
Di = 0 表示忍者 i 面對右方；Di = 1 表示忍者 i 面對上方；Di = 2 表示忍者 i 面對左方；Di = 3 表示忍者 i 面對下方。
對於所有測資，$1\leq N\leq 10^ 5; 1\leq W,H\leq 10^ 9; 1\leq X_i\leq W; 1\leq Y_i\leq H$。
$N,W,H\leq 1000$的測試資料佔分 10%。
$N\leq 1000$的測試資料佔分 40%。
Output Format
輸出在 W×H 方陣中經過足夠的時間後，苦無飛行過的格子數量。
Sample Input 1
5
3 3 2
3 2 0
4 2 2
5 4 1
1 1 3
Sample Output 1
Sample Input 2
12
3 2 3
6 3 2
7 1 3
1 5 0
3 6 1
6 6 1
4 5 2
1 3 0
6 5 2
5 1 2
6 4 3
4 1 3
Sample Output 2
Hints
Problem Source
APIO 2012
Set by Yihda Yol
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0~2 | 10 |
| 2 | 0~9 | 30 |
| 3 | 0~23 | 60 |