连连看游戏中的配对路径搜索
在连连看游戏中,两个图案可以消去的条件是:
- 两者图案相同。
- 两种直接存在一条通路,它是一条只经过没有图案的地方、且转折点不超过2个的折线。满足此条件的两个图案被称为是可相连的。
要判断条件1非常容易,所以主要考虑怎样判断条件2。举一个具体的例子如下,图中空格表示没有图案的地方,字母和#
表示图案,-+|
表示路径。
### ##A#
# ### |#
+-----+#
A#######
在这个例子中,A和A是可相连的。图中所给出的路径含有两个转折点。
对于此类问题,能否给出一个普遍的判断方法?在实际问题中(例如在连连看游戏里),如果判定两个图案是可相连的,还要指出一条具体的路径。
继续阅读 →