给定一个 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)求模的结果。
————————————————分割の线——————————————————
首先根据题意，得到颜色数应大于等于步数，不等式表达式为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; }写的不好，如果有纰漏，请在评论区指出。
