【Dfs剪枝+二进制】CodeForces 293B 独特的路径

xiaoxiao2021-02-28  34

【问题描述】

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

【输入数据】

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

【输出数据】

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

【输入样例 1】
2 2 4 0 0 0 0
【输出样例 1】
48
【输入样例 2】
2 2 4 1 2 2 1
【输出样例 2】
0
【输入样例 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】
3628800
【输入样例 4】
2 6 10 1 2 3 4 5 6 0 0 0 0 0 0
【输出样例 4】
4096

————————————————分割の线——————————————————

分析

首先根据题意,得到颜色数应大于等于步数,不等式表达式为n+m-1<=k 所以,

if(n+m-1>k) { cout<<'0'<<endl; return 0; }

根据如上得到的结论一,可以得到实际只有在n+m<=11的情况下才有可能有解,数据范围偏小,可以进行Dfs

但是不幸的是这仍需要二进制优化、可行性剪枝与对称性剪枝(又叫对偶性剪枝) 二进制优化:用二进制的第i位的来表示第i种颜色是否在从(1,1)到(x,y)的某条路径中出现过(即不能再被使用) 可行性剪枝:如果可用颜色数小于剩余步数,则返回0 对偶性剪枝:如果某种颜色被第一次使用,则其他在此点的第一次使用的颜色所形成的方案数应与其等价,则不必再次Dfs

哦,切记取模

如有请查看代码间注释:

#include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; #define M 12 #define P 1000000007 int m,n,k; int a[M][M],num[M],f[M][M]; int logn[2000]; int dfs(int x,int y) { if(y==m+1) { y=1; x++; } if(x==n+1) return 1;//每个格点一个个确定颜色 int ret=0,d=-1,now=f[x-1][y]|f[x][y-1],c=0;//now表示到(x,y)不可以用的所有颜色 for(int i=now;i;i-=i&(-i))c++;//统计now中使用颜色的个数 if(m+n-x-y+1>k-c)return 0;//如果剩余颜色数小于步数,可行性剪枝 int can=(~now)&((1<<k)-1);//提取那些可以放颜色的点 for(int i=can;i;i-=i&(-i)) { int temp=i&(-i);//巧用补码求最低位的1 int t=logn[temp];//以2为底求指数(即求颜色的序号) if(a[x][y]==0||a[x][y]==t) { f[x][y]=now|temp;//到达f[x][y]时使用颜色的情况 num[t]++;//颜色为t的个数++ if(num[t]==1)//对偶剪枝 { if(d==-1)d=dfs(x,y+1);//如果颜色第一次出现,那其他第一次出现的颜色方案数应相同 ret+=d;//再次出现不需要再次dfs } else if(num[t])ret+=dfs(x,y+1);//普通dfs ret%=P; num[t]--;//回溯,将(x,y)变为空 } } return ret; } int main() { freopen("path.in","r",stdin); freopen("path.out","w",stdout); scanf("%d%d%d",&n,&m,&k); if(n+m-1>k) { cout<<'0'<<endl; return 0; } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { scanf("%d",&a[i][j]); if(a[i][j])num[a[i][j]]++;//如果有颜色,则颜色为a[i][j]的个数++ } for(int i=1;i<=k;i++) logn[1<<(i-1)]=i;//将第i位为1时的十进制数与第i位对应(方便log的取位) cout<<dfs(1,1)%P;//输出从(1,1)到(n,m)的颜色涂色方案 return 0; }

写的不好,如果有纰漏,请在评论区指出。

转载请注明原文地址: https://www.6miu.com/read-2800062.html

最新回复(0)