题解 P1817 【棋盘染色_NOI导刊2011提高（03）】

VenusM1nT · 2018-12-21 16:03:45 · 题解

古代评测姬怎么比现在快那么多啊QAQ

啊算了不管了

这道题……和P4537 [CQOI2007]矩形基本一模一样，但是这道题每种不同的分割方式，如果把黑白颜色交换是不同的方式，所以做法就是两趟爆搜分界线，从左侧和下侧开始爆搜，然后答案乘上2

此时你会光荣的收到TLE\times 3，但是这道题因为是一道计数的爆搜题，所以基本上应该是没有办法剪枝的，于是我们此时除了开O2（不知道能不能AC）还有什么办法呢？

回头看看数据范围，n\leq 7,m\leq 8，想到了什么？

没错，打表啊！

于是我们打表即可AC~

（注意，(7,8)这组极限数据要开long\ long）

打表程序：

#include<bits/stdc++.h>
using namespace std;
int n,m;
long long ans;
int dx[]={0,1,-1,0,0},dy[]={0,0,0,1,-1};
bool vis[15][15];
void Dfs(int x,int y)
{
    if(x<1 || x>=n || y<1 || y>=m) ans++;
    else
    {
        vis[x][y]=1;
        for(int i=1;i<=4;i++)
        {
            int nx=x+dx[i],ny=y+dy[i];
            if(!vis[nx][ny]) Dfs(nx,ny);
        }
        vis[x][y]=0;
    }
}
int main()
{
    freopen("1.txt","r",stdin);
    freopen("ans2.txt","w",stdout);
    while(cin>>n>>m)
    {
        ans=0;
        for(int i=1;i<n;i++)
        {
            memset(vis,0,sizeof(vis));
            vis[i][0]=1;
            Dfs(i,1);
        }
        for(int i=1;i<m;i++)
        {
            memset(vis,0,sizeof(vis));
            vis[0][i]=1;
            Dfs(1,i);
        }
        printf("    else if(n==%d && m==%d) cout<<\"%lld\"<<endl;\n",n,m,ans*2);
    }
    return 0;
}