蓝桥杯方格分割

标题：方格分割

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

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

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

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

解题思路：题目要求沿着格子的边线剪成两个部分，仔细观察，剪开的边线是关于中心点（3，3）对称的，于是我们从点（3，3）开始搜索，

直到搜到边界则退出。需要注意的是要从（3，3）点开始向两个方向同时搜索，并且这里两个方向是相反的。最后得出的结果要除以4，因为旋转堆成的也属于同一种分割法。

 1 #include<iostream>  
 2 #include<cstring>
 3 
 4 using namespace std;
 5 
 6 int dx[] = {1,-1,0,0};
 7 int dy[] = {0,0,1,-1};
 8 int vis[7][7];
 9 int result = 0;
10 
11 void dfs(int x, int y)
12 {
13     if(x == 0 || x == 6 || y == 0 || y == 6)
14     {
15         result++;
16         return;
17     }
18     
19     for(int i = 0; i < 4; ++i)
20     {
21         int x1 = x + dx[i];
22         int y1 = y + dy[i];
23         
24         int x2 = 6 - x1;
25         int y2 = 6 - y1;
26         
27         if(!vis[x1][y1])
28         {
29             vis[x1][y1] = 1;
30             vis[x2][y2] = 1;
31             
32             dfs(x1, y1);
33             
34             vis[x1][y1] = 0;
35             vis[x2][y2] = 0;
36             
37         }
38     }
39 } 
40 
41 
42 int main()
43 {
44     memset(vis, 0, sizeof(vis));
45     vis[3][3] = 1;
46     dfs(3,3); 
47     cout << result/4 << endl;         
48     
49     return 0;
50 }

最终答案： 509

蓝桥杯 方格分割

蓝桥杯方格分割