1519 . [APIO '12] 苦無問題
TopCoder
Description
苦無（Kunai）是一個刀子形狀的尖銳武器，忍者會對他們的敵人投擲苦無。
現在有 $N$ 名忍者在 $H$ 列 $W$ 行的方陣中，每名忍者在格子的正中央，並且一個格子不會有兩名以上的忍者。每名忍者都有一把苦無，並且面向上、下、左、右四個方向中的其中一個方向。在時間點 $0$ 時，每名忍者朝他們面向的方向投擲出苦無。
每把苦無以速度 $1$ 直線前進，如果有不止一把苦無在同一時間飛到同一地點，它們會破撞並且消失。我們可以忽略苦無的大小。另外，由於忍者可以快速移動，所以他們不會被苦無擊中。每把苦無會以等速直線飛行，除非和另外的苦無碰撞。
在下圖中，箭頭代表苦無，箭頭方向代表苦無飛行的方向，在這些圖中，所有粗體的箭頭都會發生碰撞。
而在下列圖中，粗箭頭並不會和另一個粗箭頭相撞。第二和第三張圖中，細箭頭會和一個粗箭頭相撞。因為相撞的箭頭會消失，因此這兩張圖中各有一個粗箭頭不會發生碰撞而會持續飛行。
請計算足夠長的時間後，在 $W \times 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$ 面對的方向。
$D_i = 0$ 表示忍者 $i$ 面對右方；$D_i = 1$ 表示忍者 $i$ 面對上方；$D_i = 2$ 表示忍者 $i$ 面對左方；$D_i = 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 \times 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
2024/07/28 Update: Added $\LaTeX$ and formatted by FHVirus
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0~2 | 10 |
| 2 | 0~9 | 30 |
| 3 | 0~23 | 60 |