leetcode 174. Dungeon Game 完美世界秋招程式設計題2

2017年完美世界秋招的原題。

騎士救公主，每個格子可能加血也可能減血。而且到達每個格子時的血量必須大于等于1，問騎士初始最小血量是多少才能保證救到公主。騎士每次隻能往右和往左走。好像可以壓縮一下空間。。。。。。這裡就不給出了.

我當時是從左上往後考慮的，一直沒搞清楚。。。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

<code>class</code> <code>Solution {</code>

<code>    </code><code>public</code> <code>int</code> <code>calculateMinimumHP(</code><code>int</code><code>[][] dungeon) {</code>

<code>        </code><code>if</code> <code>(dungeon == </code><code>null</code> <code>|| dungeon.length == </code><code>0</code> <code>|| dungeon[</code><code>0</code><code>].length == </code><code>0</code><code>) </code><code>return</code> <code>0</code><code>;</code>

<code>    </code> 

<code>    </code><code>int</code> <code>m = dungeon.length;</code>

<code>    </code><code>int</code> <code>n = dungeon[</code><code>0</code><code>].length;</code>

<code>        </code><code>///走到m,n時所需要的最少血量</code>

<code>        </code><code>int</code><code>[][] health = </code><code>new</code> <code>int</code><code>[m][n];</code>

<code>        </code><code>///最後是整數的話，隻需要一滴血就行，負數的話就是1+血</code>

<code>        </code><code>health[m-</code><code>1</code><code>][n-</code><code>1</code><code>] = Math.max(</code><code>1</code><code>,</code><code>1</code><code>-dungeon[m-</code><code>1</code><code>][n-</code><code>1</code><code>]);</code>

<code>        </code><code>//最後一列</code>

<code>        </code><code>for</code><code>(</code><code>int</code> <code>i = m-</code><code>2</code><code>; i&gt;=</code><code>0</code> <code>;i--)</code>

<code>            </code><code>health[i][n-</code><code>1</code><code>] = Math.max(</code><code>1</code><code>,health[i+</code><code>1</code><code>][n-</code><code>1</code><code>] - dungeon[i][n-</code><code>1</code><code>]);</code>

<code>        </code><code>///最後一行</code>

<code>        </code><code>for</code><code>(</code><code>int</code> <code>j = n-</code><code>2</code><code>; j&gt;=</code><code>0</code><code>;j--){</code>

<code>            </code><code>health[m-</code><code>1</code><code>][j] = Math.max(</code><code>1</code><code>,health[m-</code><code>1</code><code>][j+</code><code>1</code><code>] - dungeon[m-</code><code>1</code><code>][j]);</code>

<code>        </code><code>}</code>

<code>        </code><code>///中間的格子</code>

<code>        </code><code>for</code><code>(</code><code>int</code> <code>i = m-</code><code>2</code><code>; i&gt;=</code><code>0</code><code>;i--){</code>

<code>            </code><code>for</code><code>(</code><code>int</code> <code>j = n-</code><code>2</code><code>;j&gt;=</code><code>0</code><code>;j--){</code>

<code>                </code><code>int</code> <code>right = Math.max(</code><code>1</code><code>,health[i][j+</code><code>1</code><code>]-dungeon[i][j]);</code>

<code>                </code><code>int</code> <code>down = Math.max(</code><code>1</code><code>,health[i+</code><code>1</code><code>][j] - dungeon[i][j]);</code>

<code>                </code><code>health[i][j] = Math.min(down,right);</code>

<code>            </code><code>}</code>

<code>        </code><code>return</code> <code>health[</code><code>0</code><code>][</code><code>0</code><code>];</code>

<code>    </code><code>}</code>

<code>}</code>

可以參考這個過程

dungeon

From the Dungeon grid, we can simply compute health for the [last row][last column].

Now we get

Now because the knight can only move rightward or downward in each step, we can compute all the health value for last row from right to left using its rightward neighbor. we can also compute all the health value for last column from bottom to up using its downward neighbor.

Now, we can compute all the health value using its downward neighbor and rightward neighbor(we use the min value of these 2 health value).

本文轉自 努力的C 51CTO部落格，原文連結:http://blog.51cto.com/fulin0532/1970147