2017年第八届蓝桥杯C++B组D题
程序员文章站
2022-03-31 08:08:44
...
2017年第八届蓝桥杯C++B组D题
方格分割
6x6的方格,沿着格子的边线剪开成两部分。
要求这两部分的形状完全相同。
如图所示就是可行的分割法。
试计算:
包括这3种分法在内,一共有多少种不同的分割方法。
注意:旋转对称的属于同一种分割法。
请提交该整数,不要填写任何多余的内容或说明文字。
哈喽,我又来补题了,我发现真的=-=就2019特简单吧=-=
其余的。。300题加油!
今天在写概率论,我真的小瞧了概率论。。。写了我一下午。。
这个题目先开始一看我知道是搜索把。。但是不知道怎么处理。。吓到我了。。
题目思路就是搜索,分别探路的那种。
然后题目说旋转对称的属于一种,仔细比较一下,你可以看到这些图形都是中心对称的,也就是说他们都是符合中心对称图形,中心对称图形满足旋转对称。。害,也就是说我们dfs的时候会把题目要求的一种方法算成四种,所以我们结果除4就可以啦
然后就是碰到边界就可以++了,因为我们dfs兵分两路,两路兵分都是对称的其实(走过的路线),然后没有走过的路线也是对称的,没有对称的+对称的,就是符合要求的分割方法。
这道题说到这里就应该很简单啦。对了,起点从(3, 3)开始就可以了,毕竟都是中心对称图形啦。
然后就是代码部分啦~
#include <bits/stdc++.h>
#define mst(a, n) memset(a, n, sizeof(a))
using namespace std;
struct node
{
int x;
int y;
};
int dir1[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int dir2[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int cnt;
int m[7][7];
int vis[10][10];
bool check(node a, node b)
{
if (!vis[a.x][a.y] && !vis[b.x][b.y])
{
if (a.x == b.x && a.y == b.y)
{
return false;
}
return true;
}
return false;
}
void dfs(node s1, node s2)
{
if (!s1.x || s1.y== 6 || !s2.x || s2.y == 6)
{
cnt++;
return ;
}
node a, b;
for (int i = 0; i < 4; i++)
{
a.x = s1.x + dir1[i][0];
a.y = s1.y + dir1[i][1];
b.x = s2.x + dir2[i][0];
b.y = s2.y + dir2[i][1];
if (check(a, b))
{
vis[a.x][a.y] = 1;
vis[b.x][b.y] = 1;
dfs(a, b);
vis[a.x][a.y] = 0;
vis[b.x][b.y] = 0;
}
}
}
int main()
{
node s1, s2;
s1.x = s1.y = 3;
s2.x = s2.y = 3;
mst(m, 0);
m[3][3] = 1;
dfs(s1, s2);
cout << cnt / 4 << endl;
return 0;
}
上一篇: 小结
下一篇: 【学习笔记】栈、队列、双端队列、优先队列