前几天面的．前面几轮都是简单题．最后一轮不会做，跪了．题目是leetcode Dungeon Game的变种，就是 positive numbe 代表走到那格可以加血，而且走到 positive number 加完血后那格数字变 0， negative numbe 表示走到那格就扣血，各子一直是 negatlve , 而且每次走到都扣血，然后可以向上下左右随意走动．就是格子可以多次经过。起点是左上，终点是右下救到公主。求最少要多少起始血量。 followup 是 print shortest path with minimum 血量。给了个例子
-5 -1 100 -1 100
-1 -1 -1 -1 -1
100 -1 -2 -2 -3
-1 -1 -1 -1 -300
50 -1 -1 -500 -7
唯一需要多次经过的情况就是正数。可以把所有相邻的正数归成一个group(bfs或dfs就可以解)，类似 number of islands。这个group里所有正数的和，可以获取。这个group 肯定是被负数包围。从一个正数的group到另一个正数的group需要穿越负数，这里就是要找负数最大的path。
那这样的话，复杂度应该是number of positive*grid的大小吧。worst case
还需要找path的
找path的话，方便的做法感觉是新建个int[n][m][2] next存下一步的坐标吧。然后bfs的过程中，也不断更新这个next的value
感觉dfs就可以了，这个path是不能回头的，因为都是负数
有仔细看了下，发现我的思路和您的不一样。我想的是正数的格子是不会重复走的，因为走一遍就置0了。多次经过的格子只有可能是负数的，为了寻找正数的格子。所以我想的是以所有正数的格子为起点做bfs或dfs，遇到之前走过的负数格子，如果当前需要的血比原来的少就继续走，如果多就不走了。
正数的格子走过就是0，可以重复走，比如
9
9 9 9
9
负数的格子确实可能重复走，为了获取正数
比如
10000
10000 -1 -1 -1 -1 100000
10000
目测可行
我觉得应该从右下出发DFS，构建另一个二维数组，数组里每个元素代表要从该元素去右下角所需的最小生命数、来的方向和步数。所以最下是生命值0 - -7 =7，然后类推正数减，负数加。可以重复访问元素，但是必须比当前的所需生命数小。递归调用，归溯的时候返回到达左上的步数，不能返回0，然后当前元素根据返回更新自己，不能到达也置空。
遍历完成之后，从左上出发BFS，选生命值最小里步数最小的走。
说漏了一点，DFS时，若生命值一样，可以用集合存方向和步数来保留多条道路，也可以只保留步数最小的一天路径。
不确定这样就解决可以重复访问的问题了，而且正数在访问过以后变为0，这个你考虑了吗？
这个规则没特别的，详细说打字太麻烦，我等会show you some codes吧。
有代码贴出来分享一下呗