P1817 题解

题意

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

思路

按照题意，一眼 DFS，可以敲出以下代码（橙题难度）：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int vis[11][11],dx[]={0,0,0,1,-1},dy[]={0,1,-1,0,0};
int n,m,ans;
void dfs(int x,int y){
    if(x==1||y==1||x==n||y==m){
        ans++;
        return;
    }
    vis[x][y]=1;
    for(int i=1;i<=4;i++){
        int X=x+dx[i],Y=y+dy[i];
        if(vis[X][Y]) continue;
        if(X>=1&&X<=n&&Y>=1&&Y<=m) dfs(X,Y);
    }
    vis[x][y]=0;
}
signed main(){
    cin>>n>>m;
    n++,m++;
    for(int i=2;i<n;i++){
        vis[i][1]=1;
        dfs(i,2);
        vis[i][1]=0;
    }
    for(int i=2;i<m;i++){
        vis[1][i]=1;
        dfs(2,i);
        vis[1][i]=0;
    }
    cout<<ans*2;
}

可这份代码是超时的：https://www.luogu.com.cn/record/69760863

跑一遍 7 8 这个数据，会发现程序直接跑到 10 s 之外了……

但再看一眼题目数据范围：

对于 100\% 的数据：n \leq 7，m \leq 8。

那么，我们可以想到打表！

对如上程序进行修改：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int vis[11][11],dx[]={0,0,0,1,-1},dy[]={0,1,-1,0,0};
int ans;
void dfs(int x,int y,int n,int m){
    if(x==1||y==1||x==n||y==m){
        ans++;
        return;
    }
    vis[x][y]=1;
    for(int i=1;i<=4;i++){
        int X=x+dx[i],Y=y+dy[i];
        if(vis[X][Y]) continue;
        if(X>=1&&X<=n&&Y>=1&&Y<=m) dfs(X,Y,n,m);
    }
    vis[x][y]=0;
}
signed main(){
    cout<<"{{},";
    for(int n1=1;n1<=7;n1++){
        cout<<"{0";
        for(int m1=1;m1<=8;m1++){
            int n=n1+1,m=m1+1;
            ans=0;
            memset(vis,0,sizeof vis);
            for(int i=2;i<n;i++){
                vis[i][1]=1;
                dfs(i,2,n,m);
                vis[i][1]=0;
            }
            for(int i=2;i<m;i++){
                vis[1][i]=1;
                dfs(2,i,n,m);
                vis[1][i]=0;
            }
            cout<<","<<ans*2;
        }
        cout<<"}";
        if(n1<8) cout<<",";
    }
    cout<<"};";
}

输出出来的就是表啦！

代码

#include<iostream>
using namespace std;
long long n,m,a[100][100]={{},{0,0,2,4,6,8,10,12,14},{0,2,12,30,56,90,132,182,240},{0,4,30,104,286,700,1598,3488,7390},{0,6,56,286,1228,4862,18368,67206,240180},{0,8,90,700,4862,32000,204294,1274660,7807790},{0,10,132,1598,18368,204294,2228788,23896710,252488208},{0,12,182,3488,67206,1274660,23896710,441524056,8056291934}};
int main(){
    cin>>n>>m;
    cout<<a[n][m];
}//@yangzd <- 致敬打表人（bs

AC 记录

附赠三倍经验：P1790 && P4537。