H********g
发帖数: 43926 | 1 【 以下文字转载自 Military 讨论区 】
发信人: TheObserver (社会观察家), 信区: Military
标 题: 麻痹。我出道算法题。考察下索南解决实际问题的能力。
发信站: BBS 未名空间站 (Sun Apr 9 11:35:06 2017, 美东)
给定MxN二维数组表示地图
用0表示可通行 1表示是障碍
给定两辆坦克a,b 起始坐标
每一步坦克各自可上/下/左/右移动一格 或者原地不动
两坦克行进中至少相隔一格距离！
再给定两个目标A，B坐标
请设计一个算法：
输入地图，以及坦克a,b, 和目标A, B 的坐标
输出：两辆坦克都抵达目标， 最小所需步数
注：
非码工索南，给出任意解法即可。
码工索南，要求线性时间复杂度。
example：
b 0 0 A 1 0 0 0
0 0 0 0 1 0 0 0
0 0 1 1 1 0 0 0
0 0 0 0 1 0 0 0
0 0 0 0 1 0 0 0
0 1 1 1 0 0 0 0
0 0 0 0 a 0 0 0
0 0 B 0 0 0 0 0 |
l*******s
发帖数: 7316 | 2 13步
b 0 0 A 1 0 0 0
1 0 0 0 1 0 0 0
2 0 1 1 1 0 0 0
3 4 5 0 1 0 0 0
6 0 6 0 1 0 0 0
5 1 1 1 0 0 0 0
4 3 2 1 a 0 0 0
0 0 B 0 0 0 0 0
【在 H********g 的大作中提到】
: 【 以下文字转载自 Military 讨论区 】
: 发信人: TheObserver (社会观察家), 信区: Military
: 标 题: 麻痹。我出道算法题。考察下索南解决实际问题的能力。
: 发信站: BBS 未名空间站 (Sun Apr 9 11:35:06 2017, 美东)
: 给定MxN二维数组表示地图
: 用0表示可通行 1表示是障碍
: 给定两辆坦克a,b 起始坐标
: 每一步坦克各自可上/下/左/右移动一格 或者原地不动
: 两坦克行进中至少相隔一格距离！
: 再给定两个目标A，B坐标
|
l*******s
发帖数: 7316 | 3 还得等1步，14步
【在 l*******s 的大作中提到】
: 13步
: b 0 0 A 1 0 0 0
: 1 0 0 0 1 0 0 0
: 2 0 1 1 1 0 0 0
: 3 4 5 0 1 0 0 0
: 6 0 6 0 1 0 0 0
: 5 1 1 1 0 0 0 0
: 4 3 2 1 a 0 0 0
: 0 0 B 0 0 0 0 0
|
t******l
发帖数: 10908 | 4 dijkstra
：【 以下文字转载自 Military 讨论区 】
：发信人: TheObserver (社会观察家), 信区: Military |
l*******s
发帖数: 7316 | 5 不是线性的
【在 t******l 的大作中提到】
: dijkstra
:
: ：【 以下文字转载自 Military 讨论区 】
: ：发信人: TheObserver (社会观察家), 信区: Military
|
t******l
发帖数: 10908 | 6 dijkstra 概念型的的 cost metric 没有线性的要求。。。具体问题可能有更巧的办法
，但 dijkstra 概念型是万金油。。。
：不是线性的
：【 在 timefall (时光崩塌) 的大作中提到: 】 |
H********g
发帖数: 43926 | 7 发信人: TheObserver (社会观察家), 信区: Military
标 题: Re: 麻痹。我出道算法题。考察下索南解决实际问题的能力。
发信站: BBS 未名空间站 (Sun Apr 9 17:26:41 2017, 美东)
哦 忘了说了，有时坦克也可以原地不动 避让 |
l*******s
发帖数: 7316 | 8 原题已经提到了。
【在 H********g 的大作中提到】
: 发信人: TheObserver (社会观察家), 信区: Military
: 标 题: Re: 麻痹。我出道算法题。考察下索南解决实际问题的能力。
: 发信站: BBS 未名空间站 (Sun Apr 9 17:26:41 2017, 美东)
: 哦 忘了说了，有时坦克也可以原地不动 避让
|
t******l
发帖数: 10908 | 9 蝗虫的意思是修改一下 Dijkstra 避免碰撞我想。
：原题已经提到了。
：【 在 Huangchong (净坛使者) 的大作中提到: 】 |
