算法學習之路|逃生

題目大意

蒜頭君在玩一款逃生的遊戲。在一個 n×m 的矩形地圖上，蒜頭位于其中一個點。地圖上每個格子有加血的藥劑，和掉血的火焰，藥劑的藥效不同，火焰的大小也不同，每個格子上有一個數字，如果格子上的數字是正數說明是一個藥劑代表增加的生命值，如果是負數說明是火焰代表失去的生命值。

蒜頭初始化有 v 點血量，他的血量上限是 c，任何時刻他的生命值都不能大于血量上限，如果血量為 0則會死亡，不能繼續遊戲。

矩形地圖上的四個角(1,1)，(1,m)，(n,1)，(n,m)為遊戲的出口。遊戲中隻要標明了一個出口，就必須朝着這個方向走。例如，選擇了左下的出口，就隻能往左和下兩個方向前進，選擇了右上的出口，就隻能往右和上兩個方向前進，左上和右下方向的出口同理。

如果成功逃生，那麼剩餘生命值越高，則遊戲分數越高。為了能拿到最高分，請你幫忙計算如果成功逃生最多能剩餘多少血量，如果不能逃生輸出 −1。

輸入格式

第一行依次輸入整數 n，m，x，y，v，c,

其中 n,m 代表地圖大小，(x,y)代表蒜頭君的初始位置，v 代表蒜頭的初始化血量，c代表蒜頭的生命值上限。

接下來 nn 行，每行有 m 個數字，代表地圖資訊。（每個數字的絕對值不大于100，地圖中蒜頭君的初始位置的值一定為 0）

輸出格式

一行輸出一個數字，代表成功逃生最多剩餘的血量，如果失敗輸出 −1。

樣例輸入

4 4 3 2 5 10

1 2 3 4

-1 -2 -3 -4

4 0 2 1

-4 -3 -2 -1

樣例輸出

10

思路：

dpi為到達此處所剩的血量。

1.當dpi-1和dpi全部小于等于0時，說明主角已挂，不可能到達這裡。

2.當max(dpi-1,dpi)+dpi > c時，血量上限不能超，即這種情況dpi=cl

狀态轉移方程：

不過需要判斷是否血量爆表，或者dp1與dp2不全能小于0.

特殊情況：

與y同行，與x同列，在這上邊dp特殊，不能左右/上下。

我的做法：先算出特殊的，後左上，右上，左下，右下。

最後得出4種結果，選擇其中大的，如果4之種都為-1，說明不可達。