Codeforces 293B Distinct Paths DFS+剪枝+状压

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题面
- 题目链接
- 题意翻译
- 输入输出样例
  - 输入样例#1
  - 输出样例#1
  - 输入样例#2
  - 输出样例#2
  - 输入样例#3
  - 输出样例#3
  - 输入样例#4
  - 输出样例#4
- 说明
思路
AC代码
总结

题面

题目链接

洛谷链接

Codeforces链接

题意翻译

【问题描述】

给定一个 $ n*m $ 的矩形色板，有 $ k $ 种不同的颜料，有些格子已经填上了某种颜色，现在需要将其他格子也填上颜色，使得从左上角到右下角的任意路径经过的格子都不会出现两种及以上相同的颜色。路径只能沿着相邻的格子，且只能向下或者向右。计算所有可能的方案，结果对 $ 1000000007 (10^9 + 7) $ 求模。

【输入数据】

第一行，三个整数 $ n, m, k (1 \leq n, m \leq 1000, 1 \leq k \leq 10) $ ；接下来 $ n $ 行，每行包含 $ m $ 个整数，表示颜色。其中 $ 0 $ 表示未涂色，非 $ 0 $ 表示颜色的编号，颜色编号为 $ 1 $ 到 $ k $ 。

【输出数据】

一行，一个整数，表示涂色方案对 $ 1000000007 (10^9 + 7) $ 求模的结果

输入输出样例

输入样例#1

输出样例#1

输入样例#2

输出样例#2

输入样例#3

5 6 10

0 0 0 0 0 0

0 0 0 0 0 0

0 0 0 0 0 0

0 0 0 0 0 0

0 0 0 0 0 0

输出样例#3

输入样例#4

2 6 10

1 2 3 4 5 6

0 0 0 0 0 0

输出样例#4

说明

【时空限制】

2000ms,256MB

思路

首先题目是吓人的。n+m-1>k的时候显然是无解的。那么输出0。

那么范围就缩小很多了。

然后就没有别的办法了。搜索吧

但是可以加这样两个剪枝

1.在填某一个格子时，如果某些颜色在之前没有使用过，那么他们的情况数都是相同的

2.如果剩余颜色不能支撑你走到终点，那就直接返回0

另外，记录颜色可以用状压

AC代码

#include<bits/stdc++.h>

const int mod=1e9+7;

const int maxn=12;

using namespace std;

int n,m,k;

int MAP[maxn][maxn],use[maxn];

int Board[maxn][maxn];

int Num(int x)

{

    int ans=0;

    while(x) x-=x&(-x),ans++;

    return ans;

}

int dfs(int x,int y)

{

    if(y==m+1) x++,y=1;

    if(x==n+1) return 1;

    int now=(Board[x-1][y]|Board[x][y-1]),kind=-1;

    int ans=0;

    if(n-x+m-y+1+Num(now)>k) return 0;

    for(int i=1;i<=k;i++)

    {

        if((1<<(i-1))&now) continue;

        if(MAP[x][y] && MAP[x][y]!=i) continue;

        Board[x][y]=((1<<(i-1))|now);

        use[i]++;

        if(use[i]==1)

        {

            if(kind==-1) kind=dfs(x,y+1);

            ans+=kind;

        }

        else ans+=dfs(x,y+1);

        ans%=mod;

        use[i]--;

    }

    return ans;

}

int main()

{

    scanf("%d%d%d",&n,&m,&k);

    if(n+m-1>k)

    {

        printf("0");

        return 0;

    }

    for(int i=1;i<=n;i++)

        for(int j=1;j<=m;j++)

        {

            scanf("%d",&MAP[i][j]);

            use[MAP[i][j]]++;

        }

    printf("%d",dfs(1,1));

    return 0;

}