蓝桥杯17届第四题——方块分割（思维，dfs）

ゝ一世哀愁。 2023-05-21 13:52 40阅读 0赞

## 方块分割 ##

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

--------------------

一开始觉得用dfs从（0,0）坐标开始分割出不同的方格图形，但是这种方格图形“不能回头”，所以会漏掉很多情况。

##### 突破口：方块分割后的图形沿着格以(3,3)中心对称。 #####

我们只要通过坐标的方式，**用dfs“绘画出可能的切割线”出一半与边界连通的图形**，即可得到一个分割方案。  
ps：描绘方向为上、下、左、右，最终ans应当除以四。

/* 因为分割后的图形完全相同，所以方格以(3,3)中心对称 用dfs“绘画出可能的切割线”出一半与边界连通的图形，即可得到一个分割方案。 */
    #include<bits/stdc++.h>
    using namespace std;
    int ans=0;
    int X[4]={ 0, 0, -1, 1};
    int Y[4]={ -1, 1, 0, 0};
    int sz[7][7];
    
    void dfs(int x, int y)
    { 
    	if(x==0||y==0||x==6||y==6)
    	{ 
    		ans++;
    		return;
    	}
    	
    
    	for(int k=0; k<4; k++)
    	{ 
    		int nx = x + X[k];
    		int ny = y + Y[k];
    		
    		//越界
    		if(nx < 0 || nx > 6 || ny < 0 || ny > 6)continue;
    		
    		//满足条件
    		if(!sz[nx][ny])
    		{ 
    			sz[nx][ny]=1;
    			sz[6-nx][6-ny]=1; 
    			dfs(nx, ny); 
    			sz[nx][ny]=0;
    			sz[6-nx][6-ny]=0;	//回溯 
    		}
    	}
    }
    
    int main()
    { 
    	memset(sz, 0, sizeof(sz));
    	sz[3][3]=1;
    	dfs(3, 3);
    	cout<<ans/4;
    	return 0;
    }

### 总结 ###

该题主要考查了思维的转变。就像可能我们发现分割后方格是中心对称，但是也没想过将（3,3）作为一个中心对称点。  
要敢想，要敢做，共勉。  
希望能够将自己的一些学习经验分享给有需要的人。  
我是小郑，一个坚持不懈的小白。

[p1]: /images/20230521/8b139706bac54ee58a6c09ab0524c876.png
[p2]: /images/20230521/f08338fc6f054563b13ddfc808d26047.png
[p3]: /images/20230521/310ad99c4a06420d914b12c14bccc7b7.png