python递归法实现简易连连看小游戏
作者:LZH_12345 发布时间:2023-04-18 12:41:02
标签: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")
程序结果显示:
python俄罗斯方块游戏集合
python经典小游戏汇总
python微信跳一跳游戏集合
来源:https://blog.csdn.net/LZH_12345/article/details/79516307
0
投稿
猜你喜欢
- binlog介绍binlog,即二进制日志,它记录了数据库上的所有改变.改变数据库的SQL语句执行结束时,将在binlog的末尾写入一条记录
- 经常有网站管理员因为各种原因和操作,导致网站数据误删,而且又没有做网站备份,结果不知所措,甚至给网站运营和盈利带来负面影响。所以本文我们将和
- 问题你想定义一个函数或者方法,它的一个或多个参数是可选的并且有一个默认值。解决方案定义一个有可选参数的函数是非常简单的,直接在函数定义中给参
- 目录Mock概念Mock类简单的例子体验下 Mock 的功能特点一个相对正式的 Mock 例子一个完整的测试例子断言方法Mock概念mock
- vue阻止页面回退的方法如何阻止页面回退?VUE中跳转页面后,阻止返回的方法有很多种,这里就不一一列举,我是用vue-prevent-bro
- MySQL中涉及的几个字符集 character-set-server/default-character-set:服务器字符集,默认情况下
- 本文较为详细的分析了了Python的对象体系。分享给大家供大家参考。具体如下:Guido用C语言创造了Python,在Python的世界中一
- 1.什么是临时表内部临时表是sql语句执行过程中,用来存储中间结果的的数据表,其作用类似于:join语句执行过程中的joinbuffer,o
- typeof都返回object在JavaScript中所有数据类型严格意义上都是对象,但实际使用中我们还是有类型之分,如果要判断一个变量是数
- Web应用中大多会提供静态文件服务以便给用户更好的访问体验。静态文件主要包含CSS样式文件,js脚本,图片和字体等。Flask也支持静态文件
- 在安装完数据库后,由于自己不小心直接关闭了安装窗口,或者长时间没有使用root用户登录系统,导致忘记了root密码,这时就需要重置MySQL
- 一 接口介绍如果说gorountine和channel是支撑起Go语言的并发模型的基石,让Go语言在如今集群化与多核化的时代成为一道亮丽的风
- 以前在windows下一直用的idel带的功能调试python程序,在linux下没调试过。(很多时候只是print)就从网上查找一下~方法
- 本文实例讲述了Python基于opencv的图像压缩算法。分享给大家供大家参考,具体如下:插值方法:CV_INTER_NN - 最近邻插值,
- 温馨提示,只想看图的画直接跳到最后一节拉格朗日方程此前所做的一切三体和太阳系的动画,都是基于牛顿力学的,而且直接对微分进行差分化,从而精度非
- 来需求了。。干活啦。。需求内容部分时候由于缓存刷新、验证码显示不出来或者浏览器打不开或者打开速度很慢等原因,导致部分测试同事不想使用浏览器登
- 如需安装运行环境或远程调试,可加QQ905733049, 或QQ2945218359由专业技术人员远程协助!运行结果如下:代码如下:impo
- 在查询中执行下列语句 EXEC sp_attach_single_file_db @dbname = 'tggov_Data'
- 引言----在实际的web测试工作中,需要配合键盘按键来操作,webdriver的 keys()类提供键盘上所有按键的操作,还可以模拟组合键
- 代码如下: 代码如下:///<summary> /// 将两个列不同的DataTable合并成一个新的DataTab