蓝桥杯-方格分割-python

题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

6x6的方格，沿着格子的边线剪开成两部分。 要求这两部分的形状完全相同。

如下就是三种可行的分割法。

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

运行限制

最大运行时间：1s最大运行内存: 128M

思路：

1.分割线一定会经过中心点，故我们在使用dfs深度优先搜索时要从（3，3）开始搜索，如果搜索到边界就停止搜索，计数

2.只要确定半条线的走向，就能依照关于原点对称的原则就可以找到另外半条线，具体体现在我们的代码中就是在标记了当前走到的点时，也要标记和它关于中心点（3，3）对称的点

3.在向四个方向搜索时，如果判断到移动后的点超出边界，则不进行搜索，如果该点被标记搜索过，也不进入搜索

代码：

count=0
vis=[[1]*7 for i in range(7)]
dir=[(-1,0),(1,0),(0,-1),(0,1)]
def dfs(x,y):
    global count
    if x==0 or y==0 or x==6 or y==6:
        count+=1
        return
    vis[x][y],vis[6-x][6-y]=0,0
    for i in range(0,4):
        newx = x+dir[i][0]
        newy = y+dir[i][1]
        if newx<0 or newy<0 or newx>6 or newy>6:
            continue
        if vis[newx][newy]:
            dfs(newx,newy)
    vis[x][y],vis[6-x][6-y]=1,1

dfs(3,3)
print(count/4)
    

 感谢蓝桥杯及华东理工大学罗老师的教程！