問題： 簡單版連連看小游戲

一個(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)

輸出要求：

對于每一組需要測試的游戲卡片輸出:
??? 若可以連接，找到線段最小路徑，輸出：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)
輸出要求：
對于每一組需要測試的游戲卡片輸出:
 若可以連接，找到線段最小路徑，輸出：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
            
            
          

程序結(jié)果顯示：

以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。