以最小方向变化进入网格

Question

有一个网格,每个单元格包含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计算从源到目标的每条路径的方向变化.报告方向变化的最小值.但它不适用于大尺寸输入.如果有人可以建议更好的方法,那么它会有所帮助.

Answer 1

第 1 阶段：首先以显而易见的方式将网格转换为图表：

1. 网格中每个有值的方块0都是一个节点（图中不需要墙节点）。
2. 为代表相邻正方形的节点添加边。此阶段所有边的值为0。

第二阶段：将图转变为方向移动图*。

观察一个节点，我们用四个迷你节点n替换它，每个节点（在心理上）代表该节点所代表的正方形的墙。仅当相关方格具有相邻方格时，迷你节点之间的边才存在。这些边缘上的值可以是（如果边缘继续该方向 - 即从左到右或从上到下）或（如果边缘“转角” - 即从右下或从右上）。01

完成后，运行 Dijkstra 或一些类似的算法。

*这是我编的名字，不用谷歌搜索。