寻找具有旋转单元的网格的最短路径

Question

我偶然发现了这样的问题：

假设您有

N

套。 每个集合都表示为给定尺寸R（行）×

C

（列）的

网格

。每个集合始终具有相同的尺寸

R

×

C

。网格中的每个单元格都可以表示为 cornered (

A

) 节点或 straight (

B

) 节点。还要考虑到：

• 每个单元A可以旋转4次
• 每个B格可以旋转2次
• 每组的网格表示从左上角的 (0,0) 开始，到右下角的 (

  R

  -1,

  C

  -1) 结束。

细胞的视觉表示：

细胞A：

L

细胞B：

_

示例

2 套，每套包含 3x3 网格。

Set 1:
start ->|A|B|A|         
        |A|B|A|         
        |B|B|A|<- finish
Set 2:
start ->|A|B|A|         
        |A|B|A|         
        |B|A|A|<- finish

Visual representation:

Set 1:
start ->|L|_|L|
        |L|_|L|
        |_|_|L|<- finish

Set 2:
start ->|L|_|L|
        |L|_|L|
        |_|L|L|<- finish

解决方案

Set 1:
start ->|2|x|x|
        |0|0|2|
        |x|x|0|<- finish

Set 2:
start ->|2|x|x|
        |0|0|2|
        |x|x|0|<- finish

说明

我们把套装1放在桌子上。

请记住，网格从左上角 (0,0) 开始到右下角 (2,2)

1. (0,0) [2] 处的单元必须旋转 2 次，因为它将用其尖端连接到起点。
2. 下一个单元格 (0,1) [0] 不需要旋转，因为它连接到 (0,0) 处的单元格
3. 下一个单元格 (1,1) [0] 不需要旋转，因为它连接到 (0,1) 处的单元格
4. (2,1) [2] 处的单元必须旋转 2 次才能将其尖端连接到 (1,1) 处的单元
5. (2,2) 处的单元确实需要旋转，因为它已经通过其尖端连接到 (2,1) 处的单元，并通过其他尖端连接到终点

问题

我正在尝试找出一种算法，但无法完全实现，我尝试过实现 BFS 但无济于事（旋转使其变得异常困难）。该算法应该找到每个单元需要多少次旋转对于每组才能连接开始到结束。集合随机填充单元格 A 随机 90 度旋转的单元格和单元格 B 随机 180 度旋转的单元格。有什么建议我应该如何处理这个问题？

编辑

1. “用它的尖端连接到开始”在视觉上意味着：
2. “旋转”是指每个细胞可以顺时针旋转90度或180度（取决于细胞类型A或B）

Answer 1

解决此类问题的通常方法是将网格扩展到三维。 每个新层的网格中的单元格都会再旋转一次“旋转”。 一层中相邻单元之间的链接的成本为 1，但您可以以零成本在各层之间移动。

现在您可以使用 Dijkstra 算法来找到从起点到终点的最短路径。 当找到路径时，使用不同的图层，可以折叠图层，因此路径是 2D 的，但单元已像在 3D 图层中一样“旋转”。