P1817 题解
Jerrlee✅
2022-02-20 18:32:45
## 题意
给定一个 $n \times m$ 的网格，每个格子可以染成黑或白色，要求所有黑色格子连通，所有白色格子连通，并且至少有一个黑色格子贴边，至少有一个白色格子贴边。问有多少种染色方法？
## 思路
按照题意，一眼 DFS，可以敲出以下代码（橙题难度）：
```cpp
#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$。
那么，我们可以想到打表！
对如上程序进行修改：
```cpp
#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<<"};";
}
```
输出出来的就是表啦！
## 代码
```cpp
#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 记录](https://www.luogu.com.cn/record/69756933)
附赠三倍经验：[P1790](https://www.luogu.com.cn/problem/P1790) && [P4537](https://www.luogu.com.cn/problem/P4537)。