判断矩阵中a到A与b到B是否存在不相交路径

核心需求是找到a到A、b到B的两条完全无交点（路径单元格无重叠，且a/b、A/B本身为不同点）的可行路径，这里给你几个实用的解法方向：

方法一：固定一条路径后验证另一条 #

这是最直观的思路，直接复用你熟悉的单源DFS/BFS逻辑：

• 第一步：用DFS/BFS找到任意一条a到A的路径，将路径上所有单元格（包括a和A）标记为临时障碍。
• 第二步：用DFS/BFS检查b能否到达B，此时不能走被标记的临时障碍。如果能，直接返回true。
• 若当前a→A的路径导致b无法到B，则撤销标记，换另一条a→A路径重试；如果所有a→A路径都不行，再反过来：先找b→B的路径标记，再检查a→A是否可行。
• 只要任意一种组合满足条件，就返回true，否则返回false。

这种方法逻辑简单，适合小规模矩阵，还可以配合剪枝（比如优先选离b/B区域更远的a→A路径）提升效率。

方法二：双状态同步搜索 #

如果想避免枚举多条路径，可以同时追踪a和b的位置，用状态搜索解决：

• 定义状态为(pos_a, pos_b)，其中pos_a是a当前位置（到达A后固定），pos_b是b当前位置（到达B后固定）。
• 每次搜索时，对未到终点的一方（或双方）进行上下左右移动：
  • 移动后的位置不能是障碍；
  • pos_a不能等于pos_b，也不能走到b已走过的路径；
  • pos_b不能走到a已走过的路径；
• 用哈希集合记录已访问过的(pos_a, pos_b)状态，避免重复搜索。
• 当pos_a到达A且pos_b到达B时，返回true；遍历完所有状态仍未满足则返回false。

这种方法状态空间为O((m*n)^2)，中等规模矩阵（如10x10以内）完全可行，效率更稳定。

方法三：前置剪枝快速排除无效场景 #

搜索前可以先做快速判断：

• 如果a→A或b→B任意一条路径本身不存在，直接返回false（比如示例2中中间全是障碍，两条路径都走不通）；
• 如果a的路径必须经过b/B，且b的路径必须经过a/A，则必然冲突，返回false。

示例验证 #

• 示例1：

  a.b 
  ..# 
  A.B
  

  先找a→A路径：a向下走两步到A，标记路径后，b向下走两步到B，无重叠，返回true。
• 示例2：

  a.b
  ### 
  A.B
  

  a和b都无法到达对应终点，直接返回false。

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