题目描述
本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。
6x6的方格,沿着格子的边线剪开成两部分。 要求这两部分的形状完全相同。
如下就是三种可行的分割法。
试计算: 包括这 3 种分法在内,一共有多少种不同的分割方法。 注意:旋转对称的属于同一种分割法。
运行限制
- 最大运行时间:1s
- 最大运行内存: 128M
思路:
1.分割线一定会经过中心点,故我们在使用dfs深度优先搜索时要从(3,3)开始搜索,如果搜索到边界就停止搜索,计数
2.只要确定半条线的走向,就能依照关于原点对称的原则就可以找到另外半条线,具体体现在我们的代码中就是在标记了当前走到的点时,也要标记和它关于中心点(3,3)对称的点
3.在向四个方向搜索时,如果判断到移动后的点超出边界,则不进行搜索,如果该点被标记搜索过,也不进入搜索
代码:
1. vis=[[1]*7 for i in range(7)] 2. dir=[(-1,0),(1,0),(0,-1),(0,1)] 3. ans=0 4. 5. def dfs(i,j): 6. global ans 7. if i==0 or j==0 or i==6 or j==6: 8. ans+=1 9. return 10. vis[i][j],vis[6-i][6-j]=0,0 11. for n in range(4): 12. new_i = i+dir[n][0] 13. new_j = j+dir[n][1] 14. if new_i<0 or new_j<0 or new_j>6 or new_i>6: 15. continue 16. if vis[new_i][new_j]: 17. dfs(new_i,new_j) 18. vis[i][j],vis[6-i][6-j]=1,1 19. 20. dfs(3,3) 21. 22. print(ans//4)
感谢蓝桥杯及华东理工大学罗老师的教程!