问一道面试题

问一道面试题

给一个二维数组， 其中
     0 代表 可以通过
     1 代表 award
    －1  代表不可以通过

给定 起始点 和 终点坐标， 找出一条最短的路径可以得到所有的 award， 这条路径上所有的点只能走一次。
如果有很多条这样的路径， 返回其中任意一个即可。否则 if no solution, 返回 0。

例子：

     [ [ 1, 0, 0, 1, 0 ],
       [ 0, 0, 1, 0, 0 ],
       [ -1, -1, -1, 0, 0 ],
       [ 0, 0, 0, 0, 0 ],
        ]

start point: (3, 1), end point : (1, 0)
a solution path : (3, 1) --> (3, 2) --> (3, 3) --> (2, 3) --> (1, 3) --> (0, 3) --> (0, 2) --> (1, 2) --> (1, 1) --> (0, 1) --> (0, 0) --> (1, 0)

if end point is (3, 4), there is no solution because (3, 4) must be touched twice.

题目出得真好！

只能想到一个backtracking的暴力法

求教

漆寺妖，不谢

楼上说漆寺妖的是看错题目了吧。。。

这题是直觉的电面原题，从起点开始递归搜索就好了，复杂度是指数级别的，不用担心。