方格分割 2017-4


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

如图:p1.png, p2.png, p3.png 就是可行的分割法。


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

请提交该整数,不要填写任何多余的内容或说明文字。


  • 轴对称图形
  • 类似迷宫,两个人对称走
  • dfs,判界为走出迷宫
  • 双重标记
  • 结果/4



ans=0
direction=[[-1,0],[1,0],[0,-1],[0,1]]
vis=[[0 for i in range(7)] for j in range(7)]
#print(vis)

def dfs(x,y):
    global ans
    if(x==0 or y==0 or x==6 or y==6):
        ans+=1
        return
    vis[x][y]=1
    vis[6-x][6-y]=1
    for k in range(4):
        newx=x+direction[k][0]
        newy=y+direction[k][1]
        if(newx<0 or newx>6 or newy<0 or newy>6):
            continue
        if not(vis[newx][newy]):
            dfs(newx,newy)
    vis[x][y]=0
    vis[6-x][6-y]=0
dfs(3,3)
print(int(ans/4))

发表评论

电子邮件地址不会被公开。 必填项已用*标注