CF293B Distinct Paths

題意

給定一個\(n\times m\)的矩形色板，有kk種不同的顏料，有些格子已經填上了某種顏色，現在需要將其他格子也填上顏色，使得從左上角到右下角的任意路徑經過的格子都不會出現兩種及以上相同的顏色。路徑只能沿著相鄰的格子，且只能向下或者向右。

計算所有可能的方案，結果對 \(1000000007 (10^9 + 7)\)

輸入及輸出格式

輸入格式

第一行，三個整數$ n, m, k (1 \le n, m \le 1000, 1 \le k \le 10)$；

接下來\(n\)行，每行包含\(m\)個整數，表示顏色。其中\(0\)表示未涂色，非\(0\)表示顏色的編號， 顏色編號為\(1\)到\(k\)。

輸出格式

一行，一個整數，表示涂色方案對$ 1000000007 (10^9 + 7)$求模的結果。

樣例

此處就不掛了：傳送門

思路

看似數據很大：\(n, m, k (1 \le n, m \le 1000, 1 \le k \le 10)\)，但是，\(k<n+m-1\) 時，可以直接輸出\(0\)。因為無法走完一條路徑（一條路徑長度為\(n+m-1\)，因為是只能向下、向右走）。

那么實際數據范圍很小，大概是$n+m-1 \le 10 $左右吧。

這么小的范圍很容易就可想到\(dfs\)。這里有兩個優化，一個是如果搜到一半，發現剩下的顏色不夠用了就直接\(return\)。還有一個就是利用顏色\(A\)與顏色\(B\)的先后次序問題，路徑\(AB\)與路徑\(BA\)并不是同一種方案，所以搜索時如果搜到是第一次時，就可以直接乘\(now\)就可以省去很多\(dfs\)。

代碼很丑，勿噴。

#include<algorithm> #include<bitset> #include<complex> #include<deque> #include<exception> #include<fstream> #include<functional> #include<iomanip> #include<ios> #include<iosfwd> #include<iostream> #include<istream> #include<iterator> #include<limits> #include<list> #include<locale> #include<map> #include<memory> #include<new> #include<numeric> #include<ostream> #include<queue> #include<set> #include<sstream> #include<stack> #include<stdexcept> #include<streambuf> #include<string> #include<typeinfo> #include<utility> #include<valarray> #include<vector> #include<cstring> #include<cmath> #define MOD 1000000007 using namespace std;//惡心的頭文件 inline int read(){char ch=getchar();int res=0,f=1;while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar();return res*f; }//讀入優化 inline void write(int zx){if(zx<0) zx=-zx,putchar('-');if(zx<10) putchar(zx+'0');else{write(zx/10);putchar(zx%10+'0');} }//輸出優化 int n,m,k,cnt[50],a[50][50],sum,f[30][30],ps,ans,vv; int dfs(int x,int y){if(y==m+1){return dfs(x+1,1);}if(x==n+1) return 1;int S=0,num=0,mar=0,res=0,las=0;f[x][y]=f[x-1][y]|f[x][y-1];for(int i=1;i<=k;i++){if(!(f[x][y]&(1<<i-1))) ++num;}if(num<n+m-x-y+1) return 0;//第一個優化if(a[x][y]==0){for(int i=1;i<=k;i++){if(!(f[x][y]&(1<<i-1))){if(cnt[i]==0){if(mar) res+=las,res%=MOD;//第二個優化else{mar=1;cnt[i]++;f[x][y]|=1<<i-1;las=dfs(x,y+1);f[x][y]^=1<<i-1;cnt[i]--;res+=las;res%=MOD;}continue ;}cnt[i]++;f[x][y]|=1<<i-1;res+=dfs(x,y+1);f[x][y]^=1<<i-1;cnt[i]--;res%=MOD;}}}else{if(!(f[x][y]&(1<<a[x][y]-1))){f[x][y]|=1<<a[x][y]-1;res+=dfs(x,y+1);f[x][y]^=1<<a[x][y]-1;res%=MOD;}}return res; } int main(){n=read();m=read();k=read();vv=n+m-1;if(k<vv){//開始先特判puts("0");return 0;}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){a[i][j]=read();cnt[a[i][j]]++;}}ans=dfs(1,1);cout<<ans<<endl;return 0; }

轉載于:https://www.cnblogs.com/yzx1798106406/p/9871478.html

總結

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

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