蓝桥杯 2017_4 分割方格(巧妙的dfs)

标题:方格分割6x6的方格,沿着格子的边线剪开成两部分。
要求这两部分的形状完全相同。如图:p1.png, p2.png, p3.png 就是可行的分割法。试计算:
包括这3种分法在内,一共有多少种不同的分割方法。
注意:旋转对称的属于同一种分割法。请提交该整数,不要填写任何多余的内容或说明文字。

思路:从对称中心开始,以格子的边与边的交点为路,把格子涂色问题,转化为划分格子边界的问题(想象剪纸,剪的是边界)

 

 

至于答案为什么要除4呢,因为对于从中心的每次搜索,都会有相反方向的一次等价的搜索,这是2次重复,此外题目说明旋转对称的也是算一种,例如上下剪出来的一定能左右也剪出来,这又是重复的,故结果要除上4。

 

 

 

 

 

 

 

 

 

#include<cstdio>
bool vis[10][10];
int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
int ans;
void dfs(int x, int y){if(x == 0 || y == 0 || x == 6 || y == 6){//剪到边界就结束了一次分割++ans;return ;}for(int i = 0 ; i < 4; ++i){int nx = x + dir[i][0];int ny = y + dir[i][1];if(vis[nx][ny]) continue;vis[nx][ny] = true;vis[6-nx][6-ny] = true;dfs(nx,ny);vis[nx][ny] = false;//回溯vis[6-nx][6-ny] = false;}}
int main(){vis[3][3] = true;dfs(3,3);printf("%d",ans/4);//除掉重复的return 0;}