DQS DQS

【CF293B】Distinct Paths 搜索

in 算法,搜索read (179) 文章转载请注明来源!

题目链接


题意是给一个n*m的地图,有k种颜色,每个方格初始为0(未被涂色)或为1~k中某个数(被涂成相应颜色),现在要求涂色,问使得从[1,1]到[n,m]的所有路径中均不存在两个格子颜色相同的方案数。

一开始我大力DP,发现不会做,看标签写着“brute force”…瞄了一眼题解才发现数据范围:

$$1<=n,m<=1000,1<=k<=10$$

于是很显然,如果路径长度大于k那么答案是0.所以这个题成了搜索。

但这个题的搜索需要优化:

1.位运算加速。可以用$f_{i,j}=f_{i-1,j} \mid f_{i,j-1}$递推,这样判定成了O(1)。
2.类似组合数的剪枝。如果当前这个点的颜色只出现了一次,那么这个点是其他颜色的话对后面造成的影响是相同的(考虑一下排列组合)。那么这个方案数只需要算一遍就可以了。
3.如果剩下可用的颜色数不足以到达终点,那么方案数是0。

然后这个题就解决了。

……我是找考试题的时候找到的这个题,觉得太难所以写了博客,后来发现需要一个搜索题所以把阅读量为3的博文删掉了,然后又觉得有点偏难,所以这篇文章是我第二遍写2333

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;

const int SZ = 12;
const int mod = 1000000007;

int mp[SZ][SZ];
int n,m,k;

int f[SZ][SZ],vis[SZ];

int dfs(int x,int y)
{
    if(y > m) x ++,y = 1;
    if(x > n) return 1;
    int d = f[x - 1][y] | f[x][y - 1];
    int ans = 0,tmp = -1;

    int xx = 0;
    for(int i = 1;i <= k;i ++)
        if(!(1 << i & d)) xx ++;
    if(n - x + m - y > xx) return 0;

    for(int i = 1;i <= k;i ++)
        if(!mp[x][y] || mp[x][y] == i)
        {
            if(1 << i & d) continue;
            f[x][y] = 1 << i | d; vis[i] ++;
            if(vis[i] == 1)
            {
                if(tmp == -1) tmp = dfs(x,y + 1);
                ans += tmp; ans %= mod;
            }
            else ans += dfs(x,y + 1);
            ans %= mod;
            vis[i] --;
        }
    return ans;
}

int main()
{
    scanf("%d%d%d",&n,&m,&k);
    if(n + m - 1 > k) puts("0");
    else
    {
        for(int i = 1;i <= n;i ++)
            for(int j = 1;j <= m;j ++)
                scanf("%d",&mp[i][j]),vis[mp[i][j]] ++;
        printf("%d",dfs(1,1));
    }
    return 0;
}
jrotty WeChat Pay

微信打赏

jrotty Alipay

支付宝打赏

文章二维码

扫描二维码,在手机上阅读!

算法搜索
最后由DQS修改于2017-07-12 01:00
发表新评论
博客已萌萌哒运行
© 2018 由 Typecho 强力驱动.Theme by Yodu
前篇 后篇
雷姆
拉姆