有一个网格,每个单元格包含0或1.有一个机器人可以在网格中水平或垂直移动.机器人的起始位置和终点位置.在从开始到结束的路径中,可能需要将其方向从水平变为垂直或从垂直变为水平.我们需要找到从头到尾移动机器人所需的最小方向变化次数.从开始到结束可能有多条路径.1表示墙,0表示通道.对于前 -
1 1 1 1 1 1 1
0 0 0 0 0 0 0
1 1 1 1 1 0 0
1 1 1 1 1 1 0
在上面的网格中,如果机器人从(1,0)开始,单元格到达(3,6)则有2条路径其中一条路径需要3个方向变化而其他路径需要1个方向变化,所以答案是1.我的方法 - 使用dfs计算从源到目标的每条路径的方向变化.报告方向变化的最小值.但它不适用于大尺寸输入.如果有人可以建议更好的方法,那么它会有所帮助.