麻痹。我出道算法题。考察下索南解决实际问题的能力。 (转载)# Joke - 肚皮舞运动
H*g
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
发信人: 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