python遞歸法實(shí)現(xiàn)簡易連連看小游戲
問題:簡單版連連看小游戲
一個(gè)分割成w*h個(gè)正方格子的矩形板上,每個(gè)正方格子可以有游戲卡,也可以沒有游戲卡
兩個(gè)游戲卡之間有一條路徑相連需滿足以下三個(gè)條件:
1.路徑只包含水平和垂直的直線段
2.路徑不能穿過別的游戲卡片
3.允許路徑臨時(shí)離開矩形板
輸入要求:
第一行包括兩個(gè)整數(shù):w 和 h ; w:矩形板的寬度,h:矩形板的長度
下面h行,每行包括w個(gè)字符,表示矩形板上卡片的分布情況:'X'代表這個(gè)地方有卡片;'O'代表無卡片
之后一行包括4個(gè)整數(shù):X1,Y1,X2,Y2(1<=X1,X2<=w;1<=Y1,Y2<=h),代表兩個(gè)卡片的位置
注意:矩形板左上角的坐標(biāo)是(1,1)
輸出要求:
對(duì)于每一組需要測(cè)試的游戲卡片輸出:
若可以連接,找到線段最小路徑,輸出:k segments(k為最優(yōu)路徑的最小線段數(shù))
若不可以連接,則輸出"impossible"
問題分析:
程序代碼:
# -*- coding: utf-8 -*- """ Created on Sat Mar 10 20:40:59 2018 @author: lizihua 問題:簡單版連連看小游戲 一個(gè)分割成w*h個(gè)正方格子的矩形板上,每個(gè)正方格子可以有游戲卡,也可以沒有游戲卡 兩個(gè)游戲卡之間有一條路徑相連需滿足以下三個(gè)條件: 1.路徑只包含水平和垂直的直線段 2.路徑不能穿過別的游戲卡片 3.允許路徑臨時(shí)離開矩形板 輸入要求: 第一行包括兩個(gè)整數(shù):w 和 h (1<=w,h<=75);w:矩形板的寬度,h:矩形板的長度 下面h行,每行包括w個(gè)字符,表示矩形板上卡片的分布情況:'X'代表這個(gè)地方有卡片;'O'代表無卡片 之后一行包括4個(gè)整數(shù):X1,Y1,X2,Y2(1<=X1,X2<=w;1<=Y1,Y2<=h),代表兩個(gè)卡片的位置 注意:矩形板左上角的坐標(biāo)是(1,1) 輸出要求: 對(duì)于每一組需要測(cè)試的游戲卡片輸出: 若可以連接,找到線段最小路徑,輸出:k segments(k為最優(yōu)路徑的最小線段數(shù)) 若不可以連接,則輸出"impossible" """ import numpy as np to=[[0,1],[1,0],[0,-1],[-1,0]] #定義方向 #定義遞歸函數(shù)---因?yàn)槊恳徊剿阉髀窂降姆绞揭粯? def search(now_x,now_y,end_x,end_y,step,f): #minstep在這里必須定義全局變量,否則,報(bào)錯(cuò) 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 #新位置有效,標(biāo)記新位置 #遞歸搜索時(shí),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("請(qǐng)輸入矩形板的寬度w和長度h:").split(' ') wh = list(map(int, wh)) #輸入h行,代表矩形卡片的分布情況 line=[[' ']*wh[0]]*wh[1] for i in range(wh[1]): line[i]=input("請(qǐng)輸入第"+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) #使用上式,會(huì)使得改變某一個(gè)值時(shí),該值所在列都會(huì)隨之一樣變化 mark=np.zeros((wh[1]+2,wh[0]+2)) #定義標(biāo)記數(shù)組,并初始化 #輸入兩個(gè)卡片的位置 ,第一張卡片now(now_x,now_y);第二張卡片end(end_x,end_y) place=input("請(qǐng)輸入兩張卡片的位置:").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為一個(gè)很大的值 #遞歸搜索路徑 search(begin_x,begin_y,end_x,end_y,0,-1) #輸出結(jié)果 if minstep<100000: print(str(minstep)+"segments") else: print("impossible")
程序結(jié)果顯示:
更多關(guān)于python游戲的精彩文章請(qǐng)點(diǎn)擊查看以下專題:
以上就是本文的全部內(nèi)容,希望對(duì)大家的學(xué)習(xí)有所幫助,也希望大家多多支持腳本之家。
相關(guān)文章
python批量設(shè)置多個(gè)Excel文件頁眉頁腳的腳本
這篇文章主要介紹了python批量設(shè)置多個(gè)Excel文件頁眉頁腳的源碼,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2018-03-03詳解NumPy中的線性關(guān)系與數(shù)據(jù)修剪壓縮
本文將通過股票均線計(jì)算的案例來為大家講解一下NumPy中的線性關(guān)系以及數(shù)據(jù)修剪壓縮的實(shí)現(xiàn),文中的示例代碼講解詳細(xì),感興趣的可以了解一下2022-05-05python中opencv K均值聚類的實(shí)現(xiàn)示例
本文主要介紹了python中opencv K均值聚類的實(shí)現(xiàn)示例,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-06-06Python處理文件的方法(mimetypes和chardet)
這篇文章主要介紹了Python處理文件的方法(mimetypes和chardet),本文給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2020-09-09OpenCV-Python實(shí)現(xiàn)人臉磨皮算法
人臉磨皮是最基礎(chǔ)的人臉美顏效果。本文介紹了OpenCV-Python實(shí)現(xiàn)人臉磨皮算法,主要包括圖像濾波,圖像融合和圖像銳化,感興趣的可以了解一下2021-06-06Python?eval()和exec()函數(shù)使用詳解
exec函數(shù)執(zhí)行的是python語句,沒有返回值,eval函數(shù)執(zhí)行的是python表達(dá)式,有返回值,exec函數(shù)和eval函數(shù)都可以傳入命名空間作為參數(shù),本文給大家介紹下Python?eval()和exec()函數(shù),感興趣的朋友跟隨小編一起看看吧2022-11-11yolov5中anchors設(shè)置實(shí)例詳解
在YOLOV5算法之中,針對(duì)不同的數(shù)據(jù)集,一般會(huì)預(yù)先設(shè)置固定的Anchor,下面這篇文章主要給大家介紹了關(guān)于yolov5中anchors設(shè)置的相關(guān)資料,文中通過實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2022-06-06