您当前的位置: 首页 >  蓝桥杯

不牌不改

暂无认证

  • 0浏览

    0关注

    422博文

    0收益

  • 0浏览

    0点赞

    0打赏

    0留言

私信
关注
热门博文

2017蓝桥杯C/C++B组国赛-瓷砖样式

不牌不改 发布时间:2022-03-15 16:59:36 ,浏览量:0

题目

题目链接

题解

DFS。

方案需要满足的要求:

  1. 只能有黄和橙两种颜色;
  2. 必须填满;
  3. 任何一种颜色都不允许同时出现在 2 × 2 2×2 2×2 的方格中;
  4. 任意一种颜色图案都必须能由 2 × 1 2×1 2×1 或 1 × 2 1×2 1×2 的长方形瓷砖拼成;
  5. 瓷砖不能切割,不能重叠,也不能只铺一部分;
  6. 只考虑组合图案,忽略瓷砖的拼缝.

举几个反例:

请添加图片描述 最后一种容易忽略。

想过二进制枚举,但是二进制枚举的话,对于枚举到的每种状态不好判断是否满足要求。所以还是得用DFS。

由于要求两种颜色的图案都要能用 2 × 1 2×1 2×1 或 1 × 2 1×2 1×2 的瓷砖拼成,所以遍历到某个格子时要分别尝试着贴黄色瓷砖和橙色瓷砖。

(如果要是只dfs一种颜色的瓷砖,另一种颜色的瓷砖贴在剩下的地方,那么这无法保证剩下的位置一定能由 2 × 1 2×1 2×1 或 1 × 2 1×2 1×2 的瓷砖拼成。你说你想在找到方案时判断一下另一种颜色的图案是否可行,这不又回归到为什么二进制枚举不好实现了嘛)

如果遍历到的这个格子已经贴上了瓷砖,那么就不能再贴瓷砖了,继续判断下一个位置;如果遍历到的格子没贴上瓷砖,则必须在这个位置贴上瓷砖(“必须填满”),可以选择黄色或橙色。对于要贴瓷砖的情况,可以选择向上下贴,也可以选择左右贴。

我们按照从上往下,从左到右的顺序DFS,即先看第一行的每一列,再看第二行的每一列。当到达每一列的倒数第二块瓷砖时,我们就要将DFS的参数调整为下一行的第一个瓷砖了。

对于上图中的第三种不合法情况,我们没有什么好的技巧,只能通过 m a p map map 存起来,每次判断完 2 × 2 2×2 2×2 的方格中是否并非全色,之后再去判断该方案是否已经保存过,没保存过说明这是新方案,统计一下。

对于方案的保存,我们可以使用二进制的方式,因为总共两种颜色。

代码
#include
using namespace std;

const int N = 3, M = 10;

int vis[N+1][M+1], ans;
unordered_map hash_;

bool check () {
	for (int i = 1;i             
关注
打赏
1662186765
查看更多评论
0.0435s