蓝桥杯第八届_方格分割

本文主要是介绍蓝桥杯第八届_方格分割，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

方格分割

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

如图：p1.png, p2.png, p3.png 就是可行的分割法。
这里写图片描述

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

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

观察可得他是一个中心对称图形，我们只需要搜索它的对称线即可。我们可以把对称线抽象为从（4，4）出发到达（1，y)，或（7，y),或(x,1),或（x,7）的路径。易知这条路径只是对称线的一半，因为另一半与这条路径关于（4，4）对称。所以我们只需要注意这条路径不能和它的关于(4,4)对称的另一半路径相交就行了。

例如
这里写图片描述

该条路线从（4,4）->(4,3)->(5,3)->(5,2)->(4,2)->(3,2)->(3,3)->(2,3)->(2,2)->(1,2)。

在搜索的过程，我们不仅要标记它走过的点，而且还要标记该点关于中心点(4,4)对称的点。

因为我们不仅要满足该条路径的每个点只走一次，而且还要满足该条路径不能和它的关于(4,4)对称的另一半路径相交。

代码如下

#include<stdio.h>
const int INF = 8;     //地图范围为1~7； int mark [INF][INF] = {0}, dir[4][2] = {1,0,0,1,-1,0,0,-1};int CenterPointX = INF/2, CenterPointY = INF/2, result = 0;void dfs(int x,int y);int main()
{mark[CenterPointX][CenterPointY] = 1;dfs(CenterPointX,CenterPointY);printf("%d\n",result/4);        //旋转对称属于同一种。所以要除以4 return 0;
}void dfs(int x,int y)
{if(x == 1 || x == INF-1 || y == 1 || y == INF-1){result++;return ;}else{for(int i=0; i < 4; i++){int nx = x + dir[i][0];int ny = y + dir[i][1];if(nx >= 1 && ny <= INF-1 && ny >= 1 && ny <= INF-1 && mark[nx][ny] == 0){/*点（x,y）关于（m,n）的对称点为(2*m-x,2*n-y) ;*/mark[nx][ny] = 1;   //标记已走过的点 mark[2 * CenterPointX - nx][2 * CenterPointY - ny] = 1;     //标记该点关于中心点对称的点dfs(nx,ny) ;mark[nx][ny] = 0;mark[2 * CenterPointX - nx][2 * CenterPointY - ny] = 0;}}}}