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 (净坛使者) 的大作中提到: 】 |