一道来源于GG一面的题目

给一个二维矩阵，像这个样子

其中点（ . ）表示一个可达的方格。（X）表示起始位置。（Y）表示目的位置。（#）表示阻塞物不能通过。
现在每次可以从一个格子跳到相邻的上下左右的一个格子中。但是不能通过阻塞物。
求从X到Y的最短路径。
这个比较简单，用BFS就好了。

Follow up。没想出来。
如果可以将其中三个阻塞物#变成可达的方格。问现在从X到Y的最短路径。
（冥冥中感觉可能是DP，f[x][y][0..3]表示转换0..3个阻塞物后到达(x,y)的最短距离。
但是还是不知道该怎么做。
求大牛指点。。

applepie11 发表于 2014-12-6 00:25
如何选择在哪里穿过障碍呢？ 您能说的再详细点儿吗

这个题目比较有意思……
首先关于障碍的理解，其实原图就是一些点，障碍的点是孤立的，邻居关系就是边。虽然是无向的，我们可以把它弄成有向图（只是边建立两次而已）。每条边的代价是1。
注意“孤立点”是没有入边的，但是可以有出边，即障碍点可以有指向非障碍点的边。这个建图要细致……
然后我们建立一个“四层”的图，每一层都和原有图一样，我们称其为第1，2，3，4层。然后，如果一个点A的邻居是障碍B，则在第i层的A点到第(i + 1)层的B点间建立一条代价为0的有向边…… 简单地说跨上一层就是把一个障碍变成空白地意思。（注意上访红字，“上一层”之后可以从障碍往外走的）。
这样，起点不变，终点可能是四层中终点的位置。方法还是bfs,注意把代价为0的边对应的所有点都“捏到”一起就可以了。

cpcs 发表于 2014-12-5 14:25
这个题目比较有意思……
首先关于障碍的理解，其实原图就是一些点，障碍的点是孤立的，邻居关系就是边。 ...

曹神这题的方法能否写一个解题报告？ 给精。

我猜这题面试官想要的答案是二分答案 + bfs验证， max是不允许通过障碍的答案，min是起点和目标的x,y坐标绝对值差的和， 然后Binary Search答案用BFS验证是否存在小于等于3个障碍的路径存在。

北美农民 发表于 2015-1-11 03:54
曹神这题的方法能否写一个解题报告？ 给精。

我猜这题面试官想要的答案是二分答案 + bfs验证， max是 ...

bfs中记录经过几个障碍好像很麻烦诶，得重新建一个class？然后里面保存两个variable，一个是当前位置，另一个是从起点到当前位置经历了多少个障碍？有没有更好的方法？

那么搞应该可以嗒

很经典的 A *

LuIIabY 发表于 2014-11-19 11:15
很经典的 A *

能否详细讲下f和h函数？

这个题我见过。。。。其实是建立一个分层的图，从障碍到它的邻居分到上一层。这样建立一个4层的有向图，每层都“差不多”。如果要穿越一个障碍，必须上一层。 注意每层的障碍是可以从下一层“进人”的，并且从障碍只能出到同层点，所以图是有向的，在这个图上bfs。

cpcs 发表于 2014-12-5 04:17
这个题我见过。。。。其实是建立一个分层的图，从障碍到它的邻居分到上一层。这样建立一个4层的有向图，每 ...

如何选择在哪里穿过障碍呢？ 您能说的再详细点儿吗

总感觉是np啊

就是一道记忆化搜索题目吧,f[x][y][z=0..3]代表到(x,y)消掉至多z个障碍所用的距离.BFS时记录当前使用了消了多少次,坐标,当前距离.如果更新f时发现已经有更优解就剪枝,否则就扩展节点继续BFS.
最后输出f[Y1][Y2][3]就好.

dydcfg 发表于 2015-1-10 17:22
就是一道记忆化搜索题目吧,f[x][y][z=0..3]代表到(x,y)消掉至多z个障碍所用的距离.BFS时记录当前使用了消了 ...

貌似不是吧。。