一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 994|回复: 11
收起左侧

[算法题] 一道来源于GG一面的题目

[复制链接] |试试Instant~ |关注本帖
fmars 发表于 2014-11-14 13:12:44 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
给一个二维矩阵,像这个样子

                               
登录/注册后可看大图

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

Follow up。没想出来。
如果可以将其中三个阻塞物#变成可达的方格。问现在从X到Y的最短路径。
(冥冥中感觉可能是DP,f[x][y][0..3]表示转换0..3个阻塞物后到达(x,y)的最短距离。
但是还是不知道该怎么做。
求大牛指点。。
1guangnian 发表于 2014-11-17 15:51:08 | 显示全部楼层
那么搞应该可以嗒
回复 支持 反对

使用道具 举报

LuIIabY 发表于 2014-11-19 11:15:31 | 显示全部楼层
很经典的 A *
回复 支持 反对

使用道具 举报

 楼主| fmars 发表于 2014-11-19 11:20:56 | 显示全部楼层

能否详细讲下f和h函数?
回复 支持 反对

使用道具 举报

cpcs 发表于 2014-12-5 04:17:16 | 显示全部楼层
这个题我见过。。。。其实是建立一个分层的图,从障碍到它的邻居分到上一层。这样建立一个4层的有向图,每层都“差不多”。如果要穿越一个障碍,必须上一层。 注意每层的障碍是可以从下一层“进人”的,并且从障碍只能出到同层点,所以图是有向的,在这个图上bfs。
回复 支持 反对

使用道具 举报

applepie11 发表于 2014-12-6 00:25:15 | 显示全部楼层
cpcs 发表于 2014-12-5 04:17
这个题我见过。。。。其实是建立一个分层的图,从障碍到它的邻居分到上一层。这样建立一个4层的有向图,每 ...

如何选择在哪里穿过障碍呢? 您能说的再详细点儿吗
回复 支持 反对

使用道具 举报

applepie11 发表于 2014-12-6 00:25:28 | 显示全部楼层
总感觉是np啊
回复 支持 反对

使用道具 举报

cpcs 发表于 2014-12-6 03:25:30 | 显示全部楼层
applepie11 发表于 2014-12-6 00:25
如何选择在哪里穿过障碍呢? 您能说的再详细点儿吗

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

使用道具 举报

dydcfg 发表于 2015-1-10 17:22:01 | 显示全部楼层
就是一道记忆化搜索题目吧,f[x][y][z=0..3]代表到(x,y)消掉至多z个障碍所用的距离.BFS时记录当前使用了消了多少次,坐标,当前距离.如果更新f时发现已经有更优解就剪枝,否则就扩展节点继续BFS.
最后输出f[Y1][Y2][3]就好.
回复 支持 反对

使用道具 举报

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

貌似不是吧。。
回复 支持 反对

使用道具 举报

北美农民 发表于 2015-1-11 03:54:12 | 显示全部楼层
cpcs 发表于 2014-12-5 14:25
这个题目比较有意思……
首先关于障碍的理解,其实原图就是一些点,障碍的点是孤立的,邻居关系就是边。 ...

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

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

使用道具 举报

圆梦梦剧场 发表于 2015-1-11 04:28:08 | 显示全部楼层
北美农民 发表于 2015-1-11 03:54
曹神这题的方法能否写一个解题报告? 给精。

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

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

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-7 21:15

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表