1011 . 傳送門
TopCoder
Tags
Description
你被困在一個大小為 $N \times M$ 的網格狀迷宮中。
在這個迷宮中，每個格子有可能是空的、牆壁、或是一個傳送門。你的任務是從左上角（格子 $(1, 1)$）開始，走到右下角（格子 $(N, M)$）。你每一步可以朝右邊或下方移動到相鄰的非牆壁的格子。當你進入一個包含傳送門的格子時，你可以選擇進入傳送門，並被傳送到任何位於更右邊和更下方（或同一行或列）且不是牆壁的格子。更精確地說，如果你在有傳送門的格子 $(x, y)$ 上，你可以選擇正常行走，或是傳送到另一個使 $x' \geq x$ 且 $y' \geq y$ 的非牆壁格子 $(x', y')$。
另外，有 $K$ 個寶箱在迷宮的一些非牆壁格子中。當你在一個有寶箱的格子時，你會打開寶箱並獲得寶箱的價值。然而，寶箱可能是被詛咒的，所以你有可能從中獲得負的價值。當你進入一個有寶箱的格子時，即使你不想要，你也必須打開寶箱。
Input Format
輸入的第一行包含三個整數 $N$、$M$ 和 $K$。
接下來的 $N$ 行每行包含一個 $M$ 個字元的字串。第 $i$ 行的第 $j$ 個字元表示位置 $(i, j)$ 的格子。字元要麼是 $\texttt{.}$、$\texttt{x}$ 或 $\texttt{p}$。
接下來的 $K$ 行每行包含三個整數 $x_i$、$y_i$ 和 $v_i$。它表示在位置 $(x_i, y_i)$ 的格子有一個價值為 $v_i$ 的寶箱。
- $1 \leq N, M \leq 1000$
- $0 \leq K \leq N \times M$
- $1 \leq x_i \leq N$
- $1 \leq y_i \leq M$
- $-10 ^ 9 \leq v_i \leq 10 ^ 9$
- 保證所有 $(x_i, y_i)$ 都是不同的且不是牆壁。
- 保證 $(1, 1)$ 和 $(N, M)$ 不是牆壁。
- 保證存在至少一條從 $(1, 1)$ 到 $(N, M)$ 的路徑。
Output Format
輸出一個整數，即你能獲得的最大價值。
Sample Input 1
3 3 3 ... .x. ... 1 3 2 3 1 -5 3 2 8
Sample Output 1
3
Sample Input 2
1 4 2 .pp. 1 3 -1 1 4 2
Sample Output 2
2
Hints
Problem Source
Subtasks
| No. | Testdata Range | Score |
|---|