连连看游戏中的配对路径搜索

在连连看游戏中,两个图案可以消去的条件是:

  1. 两者图案相同。
  2. 两种直接存在一条通路,它是一条只经过没有图案的地方、且转折点不超过2个的折线。满足此条件的两个图案被称为是可相连的。

要判断条件1非常容易,所以主要考虑怎样判断条件2。举一个具体的例子如下,图中空格表示没有图案的地方,字母和#表示图案,-+|表示路径。

          
 ### ##A# 
 # ### |# 
 +-----+# 
 A####### 
          

在这个例子中,A和A是可相连的。图中所给出的路径含有两个转折点。

对于此类问题,能否给出一个普遍的判断方法?在实际问题中(例如在连连看游戏里),如果判定两个图案是可相连的,还要指出一条具体的路径。

继续阅读 →