783 . 燃燒的森林
TopCoder
Tags
Description
實驗室警鈴大作，你聽廣播後得知在 $t$ 秒前，位於 $V$ 有人不小心將試管打破，導致病毒外漏。該病毒傳播迅速，如果在某個時間內某個區域已經有病毒，則下一秒病毒就會擴散到相鄰的區域。因為該種病毒很怕陽光，所以有陽光的區域不會有病毒。整個實驗室唯一有陽光的地方是 $S$，你現在在 $P$，你決定逃到 $S$，等待救援。你每秒只能從當前的區域移動到相鄰的區域，並且你不想到有病毒的區域，因為沒有人知道這個病毒的副作用是什麼。
Input Format
第一行有三個整數 $n, m, t,\ (1\leq n, m\leq1000,\ 0\leq t\leq1000000)$，代表實驗室的大小為 $n\times m$，並且 $t$ 秒前試管被打破。
接下來有 $n$ 行，每行是一個長度為 $m$ 的字串。這 $n$ 行是實驗室的地圖，左上角為 $(0, 0)$，右下角是 $(n-1, m-1)$，標記為* 的是牆壁，人和病毒都不能通行；標記為 P 的是你現在的位置；標記為V 的是病毒外漏的區域；標記為 S 的是有陽光的區域；剩下的區域則標記為 .。
Output Format
若可以到達 $S$，請輸出最少需要幾秒；若無法到達 $S$，請輸出 Goodbye world!。
Sample Input 1
3 3 0
VS.
P*.
...
VS.
P*.
...
Sample Output 1
6
Sample Input 2
5 4 1
..S.
*.*.
V.*.
*P*.
....
..S.
*.*.
V.*.
*P*.
....
Sample Output 2
8
Hints
Problem Source
TOIJ 1013
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資 | 0 |
| 2 | 0~12 | 無額外限制 | 100 |