2017河南省B组蓝桥杯真题(1) 方格分割
程序员文章站
2022-03-31 08:09:32
...
6x6的方格,沿着格子的边线剪开成两部分。
要求这两部分的形状完全相同。
如图:p1.png, p2.png, p3.png 就是可行的分割法。
试计算:
包括这3种分法在内,一共有多少种不同的分割方法。
注意:旋转对称的属于同一种分割法。
请提交该整数,不要填写任何多余的内容或说明文字。
#include <bits/stdc++.h>
using namespace std;
int vis[10][10];
int Count;
void dfs(int Ax,int Ay,int Bx,int By){
if(Ax==Bx && Ay==By){
Count++;
return ;
}
if(Ax>2 && vis[Ax-1][Ay]==0){
vis[Ax-1][Ay]=vis[Bx+1][By]=1;
dfs(Ax-1,Ay,Bx+1,By);
vis[Ax-1][Ay]=vis[Bx+1][By]=0;
}
if(Ax<6 && vis[Ax+1][Ay]==0){
vis[Ax+1][Ay]=vis[Bx-1][By]=1;
dfs(Ax+1,Ay,Bx-1,By);
vis[Ax+1][Ay]=vis[Bx-1][By]=0;
}
if(Ay>2 && vis[Ax][Ay-1]==0){
vis[Ax][Ay-1]=vis[Bx][By+1]=1;
dfs(Ax,Ay-1,Bx,By+1);
vis[Ax][Ay-1]=vis[Bx][By+1]=0;
}
if(Ay<6 && vis[Ax][Ay+1]==0){
vis[Ax][Ay+1]=vis[Bx][By-1]=1;
dfs(Ax,Ay+1,Bx,By-1);
vis[Ax][Ay+1]=vis[Bx][By-1]=0;
}
}
int judge(int x,int y){
memset(vis,0,sizeof(vis));
Count = 0;
if(x==1)x++;
vis[x][y]=vis[8-x][8-y]=1;
dfs(x,y,8-x,8-y);
return Count;
}
int main(){
int ans=0;
for(int i=2;i<=6;i++)ans+=judge(1,i);
cout<<ans<<endl;
}