给定一个 $n\cdot m$ 的方格图,每个格子可以被染成黑色或白色,且与其相邻的四个格子中至多只有一个与其颜色相同,求方案数.
我们可以一行一行的考虑 首先假如第一行存在连续的两个1 那么后面的状态就全部可以推出 因为下面两个肯定是0 然后所有状态就可以一步步推出来 相邻没有连续的只有一种情况即101010...注意我们此时只考虑一个大类 实际上01可以取反所以最后算出的状态要乘2
在101010...的情况下 第一行没有影响 所以第一列会产生影响 这种情况和之前一样 所以我们只要考虑第一行或者第一列合法的有多少状态即可 要么一个要么两个 其实这就是斐波那契数列 当然我们也可以写一个dp