锐客网

  1. 首页 > it技术 > >

蓝桥杯|蓝桥python——方格分割【2017 第四题】

蓝桥杯算法PythonleetcodeDFS动态规划

蓝桥python——方格分割【2017 第四题】 题目描述：6x6 的方格，沿着格子的边线剪开成两部分。 要求这两部分的形状完全相同。
如图 就是可行的分割法。
【蓝桥杯|蓝桥python——方格分割【2017 第四题】】蓝桥杯|蓝桥python——方格分割【2017 第四题】
文章图片

试计算： 包括这 3 种分法在内，一共有多少种不同的分割方法。
注意：旋转对称的属于同一种分割法。
用dfs算法

def dfs(x,y): global N,count,dire,staq##声明为全局变量 if x==0 or x==N or y==0 or y==N: count+=1 return for i in range(4): xt=int(x+dire[i][0]) yt=int(y+dire[i][1]) if staq[xt][yt]: continue staq[xt][yt]=True staq[N-xt][N-yt]=True dfs(xt,yt) staq[xt][yt]=False staq[N-xt][N-yt]=False N=6 count=0 dire=[(0,1),(1,0),(0,-1),(-1,0)]##记录四个方位 staq=[[False for _ in range(N+1)] for _ in range(N+1)]##记录各个点是否被剪 staq[N//2][N//2]=Truedfs(N/2,N/2) print(count/4)

    推荐阅读


    上一篇：MySQL|MySQL知识点串讲【适用于中高级开发】-持续更新

    下一篇：蓝桥杯|蓝桥python——玩具蛇