题目链接
题解DFS。
方案需要满足的要求:
- 只能有黄和橙两种颜色;
- 必须填满;
- 任何一种颜色都不允许同时出现在 2 × 2 2×2 2×2 的方格中;
- 任意一种颜色图案都必须能由 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一种颜色的瓷砖,另一种颜色的瓷砖贴在剩下的地方,那么这无法保证剩下的位置一定能由 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
关注
打赏
最近更新
- 深拷贝和浅拷贝的区别(重点)
- 【Vue】走进Vue框架世界
- 【云服务器】项目部署—搭建网站—vue电商后台管理系统
- 【React介绍】 一文带你深入React
- 【React】React组件实例的三大属性之state,props,refs(你学废了吗)
- 【脚手架VueCLI】从零开始,创建一个VUE项目
- 【React】深入理解React组件生命周期----图文详解(含代码)
- 【React】DOM的Diffing算法是什么?以及DOM中key的作用----经典面试题
- 【React】1_使用React脚手架创建项目步骤--------详解(含项目结构说明)
- 【React】2_如何使用react脚手架写一个简单的页面?