正題

題目鏈接:https://jzoj.net/senior/#contest/show/3008/1

---

題目大意

$n?m$的格子，$k$種顏色涂色，求有多少種方案使得沒有任意一條只往右和下的路徑經過相同顏色。

---

解題思路

顯然如果$n+m?1>k$就無解，所以$n+m?1$最大為$10$，考慮搜索。

兩個剪枝

可行性剪枝:如果剩下可用顏色不超過剩下步驟，那么直接退出。

對稱性剪枝:如果有若干種顏色目前都沒有使用過，那么這個格子選擇任何一種顏色答案是一樣的。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=15; int n,m,k,a[N][N],f[N][N],v[N]; int dfs(int x,int y) {if(y>m) x++,y=1;if(x>n) return 1;int ans=0,tmp=-1,num=0;int z=f[x-1][y]|f[x][y-1];while(z) num++,z-=(z&-z);if(n+m-x-y+1>k-num) return 0;for(int i=1;i<=k;i++){if(a[x][y]&&a[x][y]!=i)continue;if((1<<i-1)&(f[x-1][y]|f[x][y-1])) continue;v[i]++;f[x][y]=f[x-1][y]|f[x][y-1]|(1<<i-1);if(v[i]==1){if(tmp==-1)tmp=dfs(x,y+1);ans+=tmp;}else ans+=dfs(x,y+1);v[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",&a[i][j]),v[a[i][j]]++;printf("%d",dfs(1,1)); }

總結

以上是生活随笔為你收集整理的jzoj4012-Distinct Paths【搜索】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。