洛谷P1817 棋盘染色 题解

题目链接：P1817 棋盘染色

题意：

给定一个 \(N \times M\) 的网格，每个格子可以染成黑色或者白色，要求所有黑色格子连通，所有白色格子连通，并且至少有一个黑色格子贴边，至少有一个白色格子贴边。问有多少种染色方法？

输入格式：

第一行有两个正整数 \(N, M\)。

输出格式：

只有一个正整数表示答案。

数据范围：

\(1 \le N \le 7\)，\(1 \le M \le 8\)。

暴力打表即可。代码如下：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)())

const int ans[10][10]={{0,2,4,6,8,10,12,14},{2,12,30,56,90,132,182,240},{4,30,104,286,700,1598,3488,7390},{6,56,286,1228,4862,18368,67206,240180},{8,90,700,4862,32000,204294,1274660,7807790},{10,132,1598,18368,204294,2228788,23896710,252488208},{12,182,3488,67206,1274660,23896710,441524056,8056291934}};
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n, m; cin >> n >> m; cout << ans[n - 1][m - 1] << '\n';
    return 0;
}

本题三倍经验（其余两题要除以 \(2\) ，原因显然）：

1. P4537 [CQOI2007] 矩形
2. P1790 矩形分割

另外本题的正解是插头dp，但是因为板子就是黑的所以我也不会。