【蓝桥杯】【2017省赛B组】【方格分割】利用DFS思想求解方格分割问题

【蓝桥杯】【2017省赛B组】【方格分割】利用DFS思想求解方格分割问题

题目来源：蓝桥杯-2017-省赛-B组
思路原著：

题目

6x6的方格，沿着格子的边线剪开成两部分。要求这两部分的形状完全相同。如图所示

试计算：
包括这3种分法在内，一共有多少种不同的分割方法。
注意：旋转对称的属于同一种分割法。
请提交该整数，不要填写任何多余的内容或说明文字。

示例

本题无示例

解题思路

在思路开始编写之前，先告知本题答案：509种
​
首先观察题目提供的三张图片，不难发现：所谓剪成两个形状完全相同的部分，其实就是 让其中一部分旋转180°后和另一部分完全重合。再根据旋转180°这个要点去观察图片，就会发现图片最中间的点是起到关键作用的点，从这一点向一条边走出一条抵达边缘的线段，然后将这个线段旋转180°，就成了符合题目要求的分割线，也就是得到了一种分割的方法。

​ 那么这一题就变成了，从中心点到边缘能够走出多少条线。（从中心蓝点走到边缘绿点）

​ 为了方便坐标描述，我们在这里统一坐标表示方式，这样与我们调试程序时观察变量也可以一一对应。

​ 首先进行算法推导

---

​ 由上图我们可以开始编写代码：

​ 首先与往常DFS编写相同，定义几个全局变量

//点的移动方向
int[] dx = {1, 0, 0, -1};
int[] dy = {0, 1, -1, 0};
//总共获得的分割方法数量
int res = 0;
//创建如同图解样式的数组，java默认所有值为0
int [][] map = new int[7][7];

​ 编写核心代码块（把点赋值成1，2，3是用来调试程序的时候方便观察）

public void get(int x, int y) {//如果传入的新点已经抵达地图边缘，则已经完成分割，计数器+1if (x == 0 || x == 6 || y == 0 || y == 6) {res++;} else {//4个不同方向对应4个stepfor (int step = 0; step < 4; step++) {//新点坐标int nx = x + dx[step], ny = y + dy[step];//新点未被探索过//注意，此处的未被探索是指新点不在当前裁剪线上if (map[nx][ny] == 0) {//新点更值map[nx][ny] = 1;//对称过去的点更值map[6 - nx][6 - ny] = 2;//传入新点坐标get(nx, ny);//路径退位，这一步很关键，退位了才能让之前的点继续上下左右移动map[nx][ny] = 0;//对称点退位map[6 - nx][6 - ny] = 0;}}}
}

调试视角与实际地图翻译预览：

​ 编写Main方法

public static void main(String[] args) {fang_ge_fen_ge demo = new fang_ge_fen_ge();//地图最中间的点直接赋值为已探索demo.map[3][3] = (3, 3);//由于起点与其他点算法相同，都会经历上下左右四个方向，但题目明确指出旋转对称的属于同一种分割法，所以此处除以4System.out.s / 4);
}

​ 代码成品

public class fang_ge_fen_ge {//点的移动方向int[] dx = {1, 0, 0, -1};int[] dy = {0, 1, -1, 0};//总共获得的分割方法数量int res = 0;//创建如同图解样式的数组，java默认所有值为0int[][] map = new int[7][7];public static void main(String[] args) {fang_ge_fen_ge demo = new fang_ge_fen_ge();//地图最中间的点直接赋值为已探索demo.map[3][3] = (3, 3);//由于起点与其他点算法相同，都会经历上下左右四个方向，但题目明确指出旋转对称的属于同一种分割法，所以此处除以4System.out.s / 4);}public void get(int x, int y) {//如果传入的新点已经抵达地图边缘，则已经完成分割，计数器+1if (x == 0 || x == 6 || y == 0 || y == 6) {res++;} else {//4个不同方向对应4个stepfor (int step = 0; step < 4; step++) {//新点坐标int nx = x + dx[step], ny = y + dy[step];//新点未被探索过//注意，此处的未被探索是指新点不在当前裁剪线上if (map[nx][ny] == 0) {//新点更值map[nx][ny] = 1;//对称过去的点更值map[6 - nx][6 - ny] = 2;//传入新点坐标get(nx, ny);//路径退位，这一步很关键，退位了才能让之前的点继续上下左右移动map[nx][ny] = 0;//对称点退位map[6 - nx][6 - ny] = 0;}}}}
}

​ 虽然本题只需要得出正确结果即可，但是并不影响我们对代码简单的优化 -> map完全不需要使用int数组，map的值是1、2、3实际上对程序都没有意义，最终程序判断的只有一句 if (map[nx][ny] == 0)，所以我们大可将map改为boolean类型。

代码实现

public class fang_ge_fen_ge {int[] dx = {1, 0, 0, -1};int[] dy = {0, 1, -1, 0};int res = 0;boolean[][] map = new boolean[7][7];public static void main(String[] args) {fang_ge_fen_ge demo = new fang_ge_fen_ge();demo.map[3][3] = (3, 3);System.out.s / 4);}public void get(int x, int y) {if (x == 0 || x == 6 || y == 0 || y == 6)res++;elsefor (int step = 0; step < 4; step++) {int nx = x + dx[step], ny = y + dy[step];if (!map[nx][ny]) {map[nx][ny] = map[6 - nx][6 - ny] = true;get(nx, ny);map[nx][ny] = map[6 - nx][6 - ny] = false;}}}
}

---

本题无执行用时和内存消耗统计