题解【P1817 棋盘染色】

· · 题解

OIer 必备技能——打表。
闲话少说，切入正题——

其实这道题一开始想到了状压，但是看到 N \le 7, M \le 8 果断暴力深搜然后打表。
这是打表代码： 

#include <iostream>
#include <cstring>
#define MAXN 100000
#define int long long
using namespace std;
int M[10][10], n, m, ans = 0;
int dx[5] = {0, 1, -1, 0, 0};
int dy[5] = {0, 0, 0, 1, -1};
void dfs(int x, int y) {
    //我觉得唯一要扯的地方就是为什么是 (x >= n) 和 (y >= m) 而不是大于
    //因为如果是大于的话，那么就可能会出现有一条黑色横杠从第 1 列到 m 列导致白色部分变成两个连通块
    //或者说有一条黑色棍子从第 1 行到第 n 行导致白色部分变成两个连通块 
    if(x < 1 || x >= n || y < 1 || y >= m) {
        ans++;
        return ;
    }
    for(int p = 1; p <= 4; p++) {
        M[x][y] = 1;
        int xx = x + dx[p], yy = y + dy[p];
        if(!M[xx][yy]) dfs(xx, yy);
        M[x][y] = 0;
    }
}
signed main() {
    freopen("if-else.txt", "w", stdout); 
    for(n = 1; n <= 7; n++)
        for(m = 1; m <= 8; m++) {
            ans = 0;
            for(int p = 1; p < n; p++) {
                memset(M, 0, sizeof(M));
                M[p][0] = 1;
                dfs(p, 1);
            }
            for(int p = 1; p < m; p++) {
                memset(M, 0, sizeof(M));
                M[0][p] = 1;
                dfs(1, p);
            }
            cout << "else if(n == " << n << " && m == " << m << ")" << " cout << " << ans * 2 << endl;
            //为什么要 * 2？因为把黑白颠倒也是一种方案，上面的 dfs 没有统计这种方案 
        }
}

然后根据这个打表代码并且对结果略微修建，我们就能得到

if(n == 1 && m == 1) cout << "0" << endl; 
else if(n == 1 && m == 2) cout << "2" << endl;
else if(n == 1 && m == 3) cout << "4" << endl;
else if(n == 1 && m == 4) cout << "6" << endl;
else if(n == 1 && m == 5) cout << "8" << endl;
else if(n == 1 && m == 6) cout << "10" << endl;
else if(n == 1 && m == 7) cout << "12" << endl;
else if(n == 1 && m == 8) cout << "14" << endl;
else if(n == 2 && m == 1) cout << "2" << endl;
else if(n == 2 && m == 2) cout << "12" << endl;
else if(n == 2 && m == 3) cout << "30" << endl;
else if(n == 2 && m == 4) cout << "56" << endl;
else if(n == 2 && m == 5) cout << "90" << endl;
else if(n == 2 && m == 6) cout << "132" << endl;
else if(n == 2 && m == 7) cout << "182" << endl;
else if(n == 2 && m == 8) cout << "240" << endl;
else if(n == 3 && m == 1) cout << "4" << endl;
else if(n == 3 && m == 2) cout << "30" << endl;
else if(n == 3 && m == 3) cout << "104" << endl;
else if(n == 3 && m == 4) cout << "286" << endl;
else if(n == 3 && m == 5) cout << "700" << endl;
else if(n == 3 && m == 6) cout << "1598" << endl;
else if(n == 3 && m == 7) cout << "3488" << endl;
else if(n == 3 && m == 8) cout << "7390" << endl;
else if(n == 4 && m == 1) cout << "6" << endl;
else if(n == 4 && m == 2) cout << "56" << endl;
else if(n == 4 && m == 3) cout << "286" << endl;
else if(n == 4 && m == 4) cout << "1228" << endl;
else if(n == 4 && m == 5) cout << "4862" << endl;
else if(n == 4 && m == 6) cout << "18368" << endl;
else if(n == 4 && m == 7) cout << "67206" << endl;
else if(n == 4 && m == 8) cout << "240180" << endl;
else if(n == 5 && m == 1) cout << "8" << endl;
else if(n == 5 && m == 2) cout << "90" << endl;
else if(n == 5 && m == 3) cout << "700" << endl;
else if(n == 5 && m == 4) cout << "4862" << endl;
else if(n == 5 && m == 5) cout << "32000" << endl;
else if(n == 5 && m == 6) cout << "204294" << endl;
else if(n == 5 && m == 7) cout << "1274660" << endl;
else if(n == 5 && m == 8) cout << "7807790" << endl;
else if(n == 6 && m == 1) cout << "10" << endl;
else if(n == 6 && m == 2) cout << "132" << endl;
else if(n == 6 && m == 3) cout << "1598" << endl;
else if(n == 6 && m == 4) cout << "18368" << endl;
else if(n == 6 && m == 5) cout << "204294" << endl;
else if(n == 6 && m == 6) cout << "2228788" << endl;
else if(n == 6 && m == 7) cout << "23896710" << endl;
else if(n == 6 && m == 8) cout << "252488208" << endl;
else if(n == 7 && m == 1) cout << "12" << endl;
else if(n == 7 && m == 2) cout << "182" << endl;
else if(n == 7 && m == 3) cout << "3488" << endl;
else if(n == 7 && m == 4) cout << "67206" << endl;
else if(n == 7 && m == 5) cout << "1274660" << endl;
else if(n == 7 && m == 6) cout << "23896710" << endl;
else if(n == 7 && m == 7) cout << "441524056" << endl;
else if(n == 7 && m == 8) cout << "8056291934" << endl;

这样一张宏伟的大表啦~
事实证明，对于这样的数据范围很小的题目，可以暴力打表然后挂机个五六分钟，就能得到答案，比如说往年的这道棋盘问题。