·【蓝桥】·蓝桥-方格分割

一道很精巧的dfs题目~

题目描述

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

lanqiao_方格分割_0.png

lanqiao_方格分割_1.png

lanqiao_方格分割_2.png

lanqiao_方格分割_3.png

题目分析

  1. 题目要求剪开后两部分形状相同，很容易想到深搜，但深搜只能一条路走到黑，我们可以对边线进行dfs！
  2. 二维矩阵不再是a[6][6]而是a[7][7]
  3. 我们发现，从中间的点a[3][3]出发，dfs(x, y)是同时进行标记
    - `a[x][y] = 1; a[6-x][6-y] = 1;`
  4. 只要走到边界，就是一种分割方法了！

***注：dfs的结果还要除以4，因为旋转对称的属于同一张分割方法

  • 答案：509
    ——————————————完整代码————————————————
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    #include <iostream>

    using namespace std;

    int a[7][7];
    int dx[] = {-1, 0, 1, 0};
    int dy[] = {0, 1, 0, -1};
    int ans = 0;
    void dfs(int x, int y){
    	if(x==0 ||y==0 || x==6 || y==6){  //走到边界就成功了
    		ans++;
    		return;
    	}
    	a[x][y] = 1;
    	a[6-x][6-y] = 1;    //对称的点也标记
    	for(int i = 0; i < 4; ++i){
    		int xe = x + dx[i];
    		int ye = y + dy[i];
    		if(a[xe][ye] == 1){
    			continue;
    		}
    		dfs(xe, ye);
    		a[xe][ye] = 0;
    		a[6-xe][6-ye] = 0;
    	}
    } 
    int main(){
    	dfs(3, 3);
    	cout << ans/4 <<endl;
    	return 0;
    }