蓝桥杯第八届_方格分割

方格分割

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;
            }

        }
    }



}