T*********r 发帖数: 2953 | 1 给定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 |
T*********r 发帖数: 2953 | 2 我看 所谓锁男擅长做题是假的! 也只擅长初中几何而已!
稍微需要动脑筋的,估计就没人会做了 |
h*********g 发帖数: 4934 | |
T*********r 发帖数: 2953 | 4 不要数字答案 图只是个 例子
要算法!
【在 h*********g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 15+9=23
|
e*g 发帖数: 4981 | |
a****n 发帖数: 3082 | 6 两坦克同时走的话,在最狭小处相遇,这是要避免的
【在 T*********r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 给定MxN二维数组表示地图 : 用0表示可通行 1表示是障碍 : 给定两辆坦克a,b 起始坐标 : 坦克各自可上下左右移动 一次走一格 : 两坦克行进中至少相隔一格距离! : 再给定两个目标A,B坐标 : 请设计一个算法: : 输入地图,以及坦克a,b, 和目标A, B 的坐标 : 输出:两辆坦克都抵达目标, 最小所需步数 : 注:
|
T*********r 发帖数: 2953 | 7 要讲究效率的话是比较难
有好的解法是线性复杂度的
【在 e*g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 太难了
|
T*********r 发帖数: 2953 | 8 不仅是狭小处
但凡各自独立的最短路径 在相同时刻有接近交叉到 都要考虑
【在 a****n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 两坦克同时走的话,在最狭小处相遇,这是要避免的
|
a****n 发帖数: 3082 | 9 那你题里没说清楚,应该是至上相隔两个格子
【在 T*********r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不仅是狭小处 : 但凡各自独立的最短路径 在相同时刻有接近交叉到 都要考虑
|
T*********r 发帖数: 2953 | 10 这不是重点。题目改成至少相隔n个格子也可以。反正要考虑互相影响就是了。
【在 a****n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 那你题里没说清楚,应该是至上相隔两个格子
|
|
|
T*********r 发帖数: 2953 | 11 其实这道题非常有实际意义 不像前面那种几何题 为了做题而做题
原型来自 机器人,无人车路径规划问题。 |
p*********r 发帖数: 7944 | |
p*********r 发帖数: 7944 | 13 第二部,把能走的路的远面都mark了。
这样范围就很小了。
recursive。 |
p*********r 发帖数: 7944 | |
a****n 发帖数: 3082 | 15 If a b距离小于一个数,让b改变路线,不要让a改变,a改变会导致步子数增加
【在 T*********r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 其实这道题非常有实际意义 不像前面那种几何题 为了做题而做题 : 原型来自 机器人,无人车路径规划问题。
|
T*********r 发帖数: 2953 | 16 观察到小距离再调整 是局部优化的做法
但我们要一个全局优化解
有的时候,也许出发的时候就该选择完全不同的一条路径
【在 a****n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : If a b距离小于一个数,让b改变路线,不要让a改变,a改变会导致步子数增加
|
a****n 发帖数: 3082 | 17 全局的话,a要13步都是0并且到达A是最优选择。同样的道理对b是9步
【在 T*********r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 观察到小距离再调整 是局部优化的做法 : 但我们要一个全局优化解 : 有的时候,也许出发的时候就该选择完全不同的一条路径
|
a****n 发帖数: 3082 | 18 所以就是循环
【在 a****n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 全局的话,a要13步都是0并且到达A是最优选择。同样的道理对b是9步
|
r******i 发帖数: 1445 | 19 思路大概是动态规划。
首先找出坦克各自的路径和步数。
再看是否路径时间有冲突。
有冲突的时候路近的让路远的。 |
T*********r 发帖数: 2953 | 20 先找独自路径无意义
我给你个简单的例子
a B 0 0 0
0 0 0 0 0
0 1 1 1 0
0 1 0 0 0
0 1 0 0 0
...
0 1 0 0 0
0 1 0 0 0
0 1 0 0 0
0 1 0 0 0
0 1 0 0 0
0 1 0 0 0
0 1 0 0 0
0 1 1 1 0
0 0 0 0 0
b A 0 0 0
独自路径都是沿着第一列走
走了很久才会发现全白走了
【在 r******i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 思路大概是动态规划。 : 首先找出坦克各自的路径和步数。 : 再看是否路径时间有冲突。 : 有冲突的时候路近的让路远的。
|
|
|
p****b 发帖数: 3 | |
T*********r 发帖数: 2953 | 22 你是码工吗
马工好意思给出这种复杂度的解 ?
【在 p****b 的大作中提到】![](/moin_static193/solenoid/img/up.png) : BFS 状态是两个坦克的位置而已。
|
h*********g 发帖数: 4934 | 23 关键看那辆车是领导的,社会不能只讲效率,还要明确长幼尊卑 |
s******r 发帖数: 5309 | 24 非马工非cs给个最不动脑子的算法
1. 列出所有起始到终点的路径 。
2. 杀掉所有路上有1的路径。
3. 杀掉所有可能相撞的路径。
4.找最短。
【在 T*********r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 给定MxN二维数组表示地图 : 用0表示可通行 1表示是障碍 : 给定两辆坦克a,b 起始坐标 : 坦克各自可上下左右移动 一次走一格 : 两坦克行进中至少相隔一格距离! : 再给定两个目标A,B坐标 : 请设计一个算法: : 输入地图,以及坦克a,b, 和目标A, B 的坐标 : 输出:两辆坦克都抵达目标, 最小所需步数 : 注:
|
T*********r 发帖数: 2953 | 25 哦 忘了说了,有时坦克也可以原地不动 避让
【在 s******r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 非马工非cs给个最不动脑子的算法 : 1. 列出所有起始到终点的路径 。 : 2. 杀掉所有路上有1的路径。 : 3. 杀掉所有可能相撞的路径。 : 4.找最短。
|
m*****n 发帖数: 4015 | 26 这个要是实际问题 比如 大到一个城市的 traffic control 的优化的话 不可能算出来
实际的全局最优。我觉得如果真是实际问题 还要单独算局部最优 然后在 做collision
detection 然后再来修正。 肯定不是一个 pass 能搞定。 |
T*********r 发帖数: 2953 | 27 说的也是啊。那我改改标题。
collision
【在 m*****n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个要是实际问题 比如 大到一个城市的 traffic control 的优化的话 不可能算出来 : 实际的全局最优。我觉得如果真是实际问题 还要单独算局部最优 然后在 做collision : detection 然后再来修正。 肯定不是一个 pass 能搞定。
|
m*****n 发帖数: 3644 | 28 夹逼法。
1,坦克a不动,找出b最短的第1,2,3,k路径。
2,b不动,找出a最短路径假设a的路径小,那么a等待让路。
3,b还是按原路竞走。动态障碍坐标为x,y,t.看a的路径是否遇到动态block。
4,如果遇到,a停1,2,3,n1步,再走,看是否遇到(假设b需要的距离长)。
5,检查是否有检查是否有只能通过一个坦克的峡谷。如果有,检查另一个坦克山包绕
路走另一条路。峡谷的定义是,长度超过b的最短的第1,2路径之差的只能过一个tank
的通道。 |
m*****n 发帖数: 3644 | 29 1,分别找出ab的最短路径
2,找出ab最短路径上的相撞点
3,相撞点记p0点,检查是否单通道。如果p0是,那么倒退1,2...k步,只到至少一方不
是。
4,检查不是单通道那方的第二路线,看绕路走多少步。
5,让不是单通道的那方等待,另一方前进,直至通过,然后等待的继续前进
6,比较4,5,看谁短。
7,如果p0不是单通道,让路径短的一方躲开2格,再回去。多走4格。 |
b*******8 发帖数: 37364 | 30 初中几何题 可以难到不用坐标法大数学家都证明不出
★ 发自iPhone App: ChineseWeb 16
【在 T*********r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我看 所谓锁男擅长做题是假的! 也只擅长初中几何而已! : 稍微需要动脑筋的,估计就没人会做了
|
|
|
b*******8 发帖数: 37364 | 31 别抬举算法了 过一千年人类还在学习平面几何公理体系 但没人搞计算机算法了 类似
宋元时代大量珠算算法都丢尽了垃圾堆
★ 发自iPhone App: ChineseWeb 16
【在 T*********r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 其实这道题非常有实际意义 不像前面那种几何题 为了做题而做题 : 原型来自 机器人,无人车路径规划问题。
|