4534 . B3. 緊急迫降（CrashLand）
TopCoder
Description
於建電中稱霸四方，比英國人還會炸魚的學術長 $Aaw$，總覺得在地球上找不到比自己更強的人類。沒有競爭對手的感覺十分無聊，因此決定航向宇宙，探索未知的區域！
然而，在資訊完全不明朗下，就隻身殺過去實在太蠢了，不符合 $Aaw$ 的作風。他本來想請乘一當敢死隊去探勘：不料阿蘇在上次一四春遊時，發現乘一實在太好玩了，就悄悄把乘一帶走，把他收歸己有，當成玩具來紓壓。無奈下 $Aaw$ 只好自己打造了一架帶鏡頭的無人機，命名為短尾袋鼠號，來暫時代替乘一的位置
然而他在製造無人機時，忘記把一個核心零件裝上去。當短尾袋鼠號飛到一半時，它的推進引擎就失靈，導致整架無人機呈自由落體落下
距離無人機落地還有一小段時間，$Aaw$ 想要尋找一塊最佳的迫降（墜機）地點，好盡可能減輕無人機的損傷，並確保自己能將其回收。此時的無人機已經無法推進自己，只得透過滑翔移動
因為他正忙著邊操控飛機，邊向周圍的人通報 Mayday.，空不出多餘的手來寫程式了。你能在飛機變成一片殘駭前，幫他找到最理想的迫降（墜機）地點嗎？
以下正文
輸入首先會給你兩張大小為 $M×N$ 的地圖
第一張記錄無人機附近的地形，由許多字元 $C$ 組成，中間以空格分離。在這些字元中，以 P 代表 Plain，D 代表 Desert，M 代表 Mountain，F 代表 Forest，O 代表 Ocean
第二張包含許多正整數 $K$，中間以空格分離。對應上一張地圖，代表各區域本身的高度，可能出現海洋比森林高這種荒謬情況（X
再接下來會輸進三個正整數 $X、Y、H$，表示無人機的初始位置（$T = 0$ 時）在 $(X, Y)$，初始高度為 $H$ 公尺。H 的值會是 $5Q ^ 2$，$Q\in \mathbb{N}$
定義左上角為 $(1, 1)$，以右下為正向，先輸入行數再輸入列數
對於 $Aaw$ 而言，迫降地形選擇的優先度為
$Plain > Desert > Mountain > Forest > Ocean$
在飛行過程中，無人機永遠遵守以下幾點 （降落不屬於飛行過程） ：
- 高度 $\geq$ 0
- 高度 > 所經地形本身之高度
- 所在位置在 (1, 1) 至 (M, N) 的範圍內
- 時間對應高度之函數為 $f(T) = H - 5\,T ^ 2$（aka 重力加速度 = 10）
- 每經過一個時間單位，都會水平移動一格，你能控制的只有它往哪個方向飛
我們定義成功降落為：
當 $f(T) = K_{i, j}$ 時，則飛機可以在第 $T$ 秒時於 $(i, j)$ 成功降落。
用中文來說，倘若此時無人機的高度 = 地形本身高度，那無人機就能在該地降落。
保證所有的地形高度都是 $f(T)$，$T \in \mathbb{N}$ 的結果。
即無人機落地的那一刻，水平上也會剛好移動到那格。因此，你不需要擔心 $T$ 是小數點的情況。
求符合以上規範的前提下，$Aaw$ 所能成功降落之地形中，優先度最高的那一個為何。若無論如何均無法成功降落（撞上其他地形或邊界），則輸出 -1
Input Format
$M\,\,N$
$C_{1, 1} \,\, C_{1, 2} \,\, ... \,\,C_{1, N}$
$C_{2, 1} \,\, C_{2, 2} \,\, ... \,\,C_{2, N}$
$...$
$C_{M, 1} \,\, C_{M, 2} \,\, ... \,\,C_{M, N}$
$K_{1, 1} \,\, K_{1, 2} \,\, ... \,\,K_{1, N}$
$K_{2, 1} \,\, K_{2, 2} \,\, ... \,\,K_{2, N}$
$...$
$K_{M, 1} \,\, K_{M, 2} \,\, ... \,\,K_{M, N}$
$X\,\,Y\,\,H$
- $1 \leq M、N \leq 100$
- $1 \leq X \leq M$ ; $1 \leq Y \leq N$
- $K_{X, Y} \leq H \leq 5×10 ^ 4$，$H = 5Q ^ 2$，$Q \in \mathbb{N}$
- $0 \leq K \leq H$，$\forall K = f(T)$，$T \in \mathbb{N}$
Output Format
請輸出在所有 可成功降落 的地形中，優先度最高的地形。
你的答案應該會是
"Plain"、"Desert"、"Mountain"、"Forest"、"Ocean"
其中一個，不包含括號
Sample Input 1
P D M
F O P
D M D
20 0 15
15 0 20
15 0 0
2 2 20
Sample Output 1
Sample Input 2
P D P
D P D
P D P
0 20 0
20 0 20
0 20 0
3 1 20
Sample Output 2
Sample Input 3
D M
O O
20 20
0 15
2 2 20
Sample Output 3
Hints
- 我比較喜歡歐系的說法，此題的 $0$ 視為自然數
- 你是不是想問為什麼飛機不會因為空氣阻力達到終端速度，我也不知道：）
- 事實上 $Aaw$ 的飛機以那個速度撞下去，是叫墜毀而非迫降
範測 1 說明
地圖大小為 3×3，初始位置在 $(2, 2)$，高度 = 20，以下將窮舉所有移動可能
:::spoiler T = 1
此時高度 = $f(1) = 15$
- 從 $(0, 0)$ 向上
此時位置在 $(1, 2)$，$15 > 0$，尚未著陸
- 從 $(0, 0)$ 向下
此時位置在 $(3, 2)$，$15 > 0$，尚未著陸
- 從 $(0, 0)$ 向左
此時位置在 $(2, 1)$，$15 = 15$，成功著陸，地形為 Forest
- 從 $(0, 0)$ 向右
此時位置在 $(2, 3)$，$0 < 20$，不符合移動條件故不得向右走
:::
:::spoiler T = 2
此時高度 = $f(2) = 0$
- 從 $(1, 2)$ 向下
此時位置在 $(2, 2)$，$0 = 0$，成功著陸，地形為 Ocean
- 從 $(1, 2)$ 向左
此時位置在 $(1, 1)$，$0 < 20$，不符合移動條件故不得向左走
- 從 $(1, 2)$ 向右
此時位置在 $(1, 3)$，$0 < 15$，不符合移動條件故不得向右走
- 從 $(3, 2)$ 向上 此時位置在 $(2, 2)$，$0 = 0$，成功著陸，地形為 Ocean
- 從 $(3, 2)$ 向左 此時位置在 $(3, 1)$，$0 < 15$，不符合移動條件故不得向左走
- 從 $(3, 2)$ 向右 此時位置在 $(3, 3)$，$0 = 0$，成功著陸，地形為 Desert ---
- 從 $(2, 1)$ 向上 此時位置在 $(1, 1)$，$0 < 20$，不符合移動條件故不得向左走
- 從 $(2, 1)$ 向下 此時位置在 $(2, 1)$，$0 < 15$，不符合移動條件故不得向下走
- 從 $(2, 1)$ 向右 此時位置在 $(2, 2)$，$0 = 0$，成功著陸，地形為 Ocean :::
綜上所述，所有可能降落的地點，有 $(2, 1)$、$(2, 2)$ 和 $(3, 3)$
地形分別為 Forest、Desert、Ocean，其中優先度最高者為 Desert
Problem Source
111學年度建北電資指定科目考試【資訊科上機考】
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~6 | 保證 $N = 1$ | 13 |
| 2 | 7~12 | 保證 $N = M = 2$ | 14 |
| 3 | 13~18 | 保證 $H \leq 5×5 ^ 2$ | 23 |
| 4 | 19~24 | 無額外限制 | 50 |