Python递归算法实现连连看路径查找与最小线段计算

落日邮差

发布时间：2026-10-13 | 5人浏览过

原创

本文介绍使用Python递归方法实现简易连连看小游戏的核心逻辑。通过定义方向数组和递归搜索函数，程序能够处理矩形板上的卡片分布，并依据水平垂直线段、不穿过其他卡片及允许出界三个条件，计算两点间连接所需的最小线段数。文章包含完整输入输出规范及代码实现，帮助开发者理解递归在路径规划中的应用。

连连看游戏问题描述

问题描述：实现一个简化版的连连看游戏逻辑。

游戏场景为一个被划分为w乘以h个正方形格子的矩形区域，每个格子内可以放置一张游戏卡片，也可以为空。

判断两张游戏卡片之间是否存在有效连接路径，必须同时满足以下三个条件：

1. 路径仅由水平或垂直的直线段组成； 2. 路径不能穿过任何其他已有的游戏卡片； 3. 路径允许暂时离开矩形板的边界范围。

输入输出规范

输入数据格式要求如下：

第一行包含两个整数w和h，分别代表矩形板的宽度和高度；接下来的h行，每行包含w个字符，用于表示矩形板上卡片的分布情况：字符'X'表示该位置有卡片，字符'O'表示该位置无卡片；随后一行包含四个整数X1、Y1、X2、Y2（其中1<=X1,X2<=w；1<=Y1,Y2<=h），分别代表待连接的两张卡片所在位置的坐标；注意：矩形板左上角的坐标定义为(1,1)。

输出结果要求如下：

对于每一组需要测试的游戏卡片对：如果存在连接路径，需找到线段数量最少的路径，输出格式为：k segments（其中k为最优路径中的最小线段数）；如果无法连接，则输出字符串："impossible"。

算法分析与代码实现

问题分析：

程序代码实现：


# -*- coding: utf-8 -*-
"""
Created on Sat Mar 10 20:40:59 2018
@author: lizihua
问题：简单版连连看小游戏
一个分割成w*h个正方格子的矩形板上，每个正方格子可以有游戏卡，也可以没有游戏卡
两个游戏卡之间有一条路径相连需满足以下三个条件：
1.路径只包含水平和垂直的直线段
2.路径不能穿过别的游戏卡片
3.允许路径临时离开矩形板
输入要求：
第一行包括两个整数：w 和 h (1<=w,h<=75);w:矩形板的宽度，h:矩形板的长度
下面h行，每行包括w个字符，表示矩形板上卡片的分布情况：'X'代表这个地方有卡片；'O'代表无卡片
之后一行包括4个整数：X1，Y1，X2，Y2(1<=X1,X2<=w;1<=Y1,Y2<=h),代表两个卡片的位置
注意：矩形板左上角的坐标是(1,1)
输出要求：
对于每一组需要测试的游戏卡片输出:
 若可以连接，找到线段最小路径，输出：k segments(k为最优路径的最小线段数)
 若不可以连接，则输出"impossible"
"""
import numpy as np
to=[[0,1],[1,0],[0,-1],[-1,0]] #定义方向
 
#定义递归函数---因为每一步搜索路径的方式一样
def search(now_x,now_y,end_x,end_y,step,f):
 #minstep在这里必须定义全局变量，否则，报错
 global minstep
 if step>minstep:
 return
 if now_x==end_x and now_y==end_y:
 if step<minstep:
 minstep=step
 return
 #枚举下一步方向 
 for i in range(4):
 x=now_x+to[i][0]
 y=now_y+to[i][1]
 
 if -1<x<(wh[1]+2) and -1<y<(wh[0]+2) and (board[x][y]=='O' and mark[x][y]==0) or (x==end_x and y==end_y and board[x][y]=='X'):
 mark[x][y]=1 #新位置有效，标记新位置
 #递归搜索时，step不变，否则，step+1
 #f代表方向，0,1,2,3代表东南西北
 if f==i:
 search(x,y,end_x,end_y,step,i)
 else:
 search(x,y,end_x,end_y,step+1,i)
 mark[x][y]=0
 
 
 
 
# h行w列 输入第一行：w=wh[0];h=wh[1]
wh=input("请输入矩形板的宽度w和长度h：").split(' ')
wh = list(map(int, wh))
 
#输入h行，代表矩形卡片的分布情况
line=[[' ']*wh[0]]*wh[1]
for i in range(wh[1]):
 line[i]=input("请输入第"+str(i+1)+"行卡片分布新情况：").split(' ')
#在矩形最外层加一圈'O'
board=np.array(line)
wide=np.array(['O']*wh[0])
high=np.array(['O']*(wh[1]+2))
#向board中的最下面加入一行'O'
board=np.insert(board,wh[1],values=wide,axis=0)
#向board中的最上面加入一行'O'
board=np.insert(board,0,values=wide,axis=0)
#向board中的最后一列加入一列'O'
board=np.insert(board,wh[0],values=high,axis=1)
#向board中的第0列加入一行'O'
board=np.insert(board,0,values=high,axis=1)
 
###注意：不要用mark=[[0]*(wh[0]+2)]*(wh[1]+2)
#使用上式，会使得改变某一个值时，该值所在列都会随之一样变化
mark=np.zeros((wh[1]+2,wh[0]+2)) #定义标记数组，并初始化
#输入两个卡片的位置 ,第一张卡片now(now_x,now_y);第二张卡片end(end_x,end_y) 
place=input("请输入两张卡片的位置：").split(' ')
place = list(map(int, place)) 
begin_x=place[0]
begin_y=place[1]
end_x=place[2]
end_y=place[3]
 
minstep=100000 #初始化minstep为一个很大的值
 #递归搜索路径
search(begin_x,begin_y,end_x,end_y,0,-1)
 #输出结果
if minstep<100000:
 print(str(minstep)+"segments")
else:
 print("impossible")

程序运行结果示例：