第八屆藍橋杯C++B組：方格分割

6x6的方格，沿着格子的邊線剪開成兩部分。

要求這兩部分的形狀完全相同。

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

試計算：

包括這3種分法在内，一共有多少種不同的分割方法。

注意：旋轉對稱的屬于同一種分割法。

請送出該整數，不要填寫任何多餘的内容或說明文字。

答案：509

思路：

1，如果以每個格子進行分割的話，使用bfs（先縱後橫（走到底）——無法切成成T字型的形狀）；

2，然後考慮以格子上的每個點，進行分割，這樣就可以使用bfs算法；

3.以正方形的中心點（3，3）【 坐标[0,6] 】，使用bfs，标注現在切割的方向和它關于中心點對稱的方向為已通路，然後向四周切割，越界時，進行下次切割；如果遇到沒有被通路，則bfs；邊界條件（當x或y，遇到0，6時，方案數+1，并傳回）

#include<cstdio>

int dire[][2]= {{-1,0}, {1,0}, {0,1}, {0,-1}};//四個方向
int vis[7][7];//是否被通路
int ans;//結果


void dfs(int x, int y){
    if(x == 0 || y == 0 || x == 6 || y == 6){//踏在裡邊線上面
        ans++;
        return;
    }
    //把目前與對稱點标記位已通路
    vis[x][y] = 1;
    vis[6 - x][6 - y] = 1;//對稱

    for (int i = 0; i < 4; ++i) {
        int dx = x + dire[i][0];
        int dy = y + dire[i][1];

        if(dx < 0 || dx > 6 || dy < 0 || dy > 6) continue;//越界

        if(!vis[dx][dy]){//沒有被通路過
            dfs(dx, dy);
        }
    }
    
    //回溯
    vis[x][y] = 0;
    vis[6 -x][6 - y] = 0;
}

int main(){
    dfs(3,3);//正方形中心點的位置
    printf("%d", ans/4);//旋轉4次都是相同的，四個方向都是對稱的
}