python递归法实现简易连连看小游戏


						问题：简单版连连看小游戏

一个分割成w*h个正方格子的矩形板上，每个正方格子可以有游戏卡，也可以没有游戏卡

两个游戏卡之间有一条路径相连需满足以下三个条件：

1.路径只包含水平和垂直的直线段

2.路径不能穿过别的游戏卡片

3.允许路径临时离开矩形板

输入要求：

第一行包括两个整数：w 和 h ; 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"

问题分析：



程序代码：





# -*- 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")



程序结果显示：



以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持中文源码网。