励志用少的代码做高效表达

问题描述：

6x6的方格，沿着格子的边线剪开成两部分。
要求这两部分的形状完全相同。
 
如图：p1.png, p2.png, p3.png 就是可行的分割法。
 
试计算：
包括这3种分法在内，一共有多少种不同的分割方法。
注意：旋转对称的属于同一种分割法。

题意分析

几种分析思路：

暴力列举： 直接枚举18个点，然后判断。 但时间耗费太高。 放弃。

对格子dfs：dfs无法识别T型图案(因为深搜只能遍历一条路)，因此放弃

想了又想， 如果对边线进行dfs，从中间点出发，最后只要用深搜能到达边界， 就代表着这条线把整个图案分成了两半。 思路就出来了！

注意：图形是可以旋转的，因此最后的结果要除以4！

剪刀剪痕与dfs边界如下图所示：

代码展示：

#include<iostream>
using namespace std;
int vis[10][10];
int dire[4][2] = { -1,0, 1,0, 0,-1, 0,1};
int ans;

void dfs(int x, int y) { 
	if(x==0 || y==6 || x==6 || y==0) { 
		ans++; return;
	}
// 当前的点标注为已访问
	vis[x][y] = 1;
	vis[6-x][6-y] = 1; 
	for(int i = 0; i < 4; i++) { 
		int tx = x+dire[i][0];
		int ty = y+dire[i][1];
// 新坐标
		if(tx<0 || tx>6 || ty<0 || ty>6) continue;
		if(!vis[tx][ty]) dfs(tx, ty); 
	}
	vis[x][y] = 0;
	vis[6-x][6-y] = 0;
}

int main() { 
	vis[3][3] = 1;
	dfs(3, 3);
	cout << ans/4 << endl;
return 0; } 

感想与总结

1、蓝桥杯的绝大多数题都是搜索或暴力，而近两年纯暴力的题越来越少，取而代之的是模拟+搜索或暴力+搜索。

2、本题就是一道非常标准的 模拟+搜索 类型题。 关于暴力+搜索，可参考2016年B组7题的剪邮票， 也很经典， 题目+题解，传送门

3、对于对称类型的题， 一定要考虑是否有重复的情况出现。

把手举过头顶，突然张开五指，那么，恭喜你给自己放了个烟花！