带可旋转单元格网格的最短路径求解算法问询

改进版状态BFS #

普通BFS失败的核心原因是未将单元格的旋转状态纳入状态维度，调整后思路如下：

• 状态定义：每个状态为(x, y, rot_state)，其中rot_state是当前单元格的旋转次数（L型取0/1/2/3，_型取0/1）。
• 初始队列：枚举起点(0,0)的所有合法旋转状态（即能向外连通的状态，比如L型旋转0次可向右/上，但起点无上方单元格，所以只保留能向右/向下的状态），将这些状态加入队列并标记已访问。
• 状态转移：
  1. 根据当前状态的单元格类型和旋转次数，确定其出口方向（比如L型旋转1次对应右、下两个出口）。
  2. 对每个出口方向，找到相邻单元格(nx, ny)。
  3. 枚举(nx, ny)的所有旋转状态，检查该状态是否包含与当前出口方向匹配的入口方向（比如当前出口是右，则相邻单元格需要有左入口）。
  4. 若匹配且该状态未被访问，将其加入队列，同时记录(nx, ny)的旋转次数为当前枚举的rot_state。
• 终止条件：当队列中出现终点(rows-1, columns-1)的合法状态时，直接返回记录的旋转次数矩阵。

约束回溯+剪枝 #

适合小规模网格，实现逻辑直观：

• 从起点开始，维护当前路径的末端位置和入口方向（起点初始无入口限制，仅关注出口）。
• 对当前单元格，枚举所有合法旋转状态，筛选出能匹配入口方向的状态并确定出口方向。
• 沿着出口方向移动到相邻单元格，重复上述步骤；若当前单元格是终点且入口方向匹配，直接返回所有旋转次数。
• 剪枝：若当前单元格的所有旋转状态都无法匹配入口方向，立即回溯到上一个单元格尝试其他状态。

并查集结合状态枚举 #

把每个单元格的每个旋转状态视为独立节点，通过合并连通节点找解：

• 节点定义：每个节点格式为(x, y, rot_state)。
• 合并规则：
  1. 对每个单元格的单个旋转状态，确认其连通的两个方向（比如_型旋转0次连通左、右）。
  2. 遍历所有相邻单元格对，比如(x,y)的某个状态有右出口，检查(x,y+1)的所有状态是否有左入口，若有则合并这两个节点。
• 解的验证：检查起点的所有合法状态节点，是否与终点的所有合法状态节点处于同一连通集合；找到目标集合后，反向推导每个单元格的旋转状态。

核心细节 #

• 必须提前明确旋转后的连通方向定义，比如：
  • L型：0次→上+右；1次→右+下；2次→下+左；3次→左+上。
  • _型：0次→左+右；1次→上+下。
• 起点/终点的特殊处理：起点无需左/上入口，只需向外出口；终点无需右/下出口，只需向内入口。

内容的提问来源于stack exchange，提问作者Dev