25行代码AC_2017年C/C++A组第四题方格分割（dfs剪痕）

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

问题描述&＃xff1a;

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

题意分析

几种分析思路&＃xff1a;

暴力列举&＃xff1a; 直接枚举18个点&＃xff0c;然后判断。 但时间耗费太高。 放弃。

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

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

剪刀剪痕与dfs边界如下图所示&＃xff1a;

代码展示&＃xff1a;

#include
using namespace std;
int vis[10][10];
int dire[4][2] &＃61; {-1,0, 1,0, 0,-1, 0,1};
int ans;void dfs(int x, int y) {if(x&＃61;&＃61;0 || y&＃61;&＃61;6 || x&＃61;&＃61;6 || y&＃61;&＃61;0) {ans&＃43;&＃43;; return;}
// 当前的点标注为已访问vis[x][y] &＃61; 1;vis[6-x][6-y] &＃61; 1; for(int i &＃61; 0; i < 4; i&＃43;&＃43;) {int tx &＃61; x&＃43;dire[i][0];int ty &＃61; y&＃43;dire[i][1];
// 新坐标if(tx<0 || tx>6 || ty<0 || ty>6) continue;if(!vis[tx][ty]) dfs(tx, ty); }vis[x][y] &＃61; 0;vis[6-x][6-y] &＃61; 0;
}int main() {vis[3][3] &＃61; 1;dfs(3, 3);cout << ans/4 << endl;
return 0; }


感想与总结

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

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

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

勿在浮沙筑高台&＃xff0c;不为浮华易匠心。 加油&＃xff0c;陌生人&＃xff01;