題目大意

給你一個n*m的網(wǎng)格，現(xiàn)在讓你往里面填1~k（有的位置已經(jīng)填了），使其滿足所有從(1,1)到(n,m)的路徑不會經(jīng)過相同的數(shù)字（只能往下或往右），求方案數(shù)

---

解題思路

對于k<n+m-1的，無法填滿任意一條路徑，特判掉

然后考慮dfs

每個位置只填左上矩陣和右下矩陣沒填過的數(shù)（保證不重），且如果當(dāng)前位置剩余顏色小于到終點的距離，那么直接特判

對于自由填的顏色（輸入沒填過），考慮到某些方案只是將顏色轉(zhuǎn)換了一下，那么讓自由填的顏色從小到大填，然后乘排列數(shù)

---

code

#include<bitset> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define N 12 #define wyc 1000000007 using namespace std; ll n,m,k,ls,ans,num,g[N],a[N][N],p[N],nx[N]; bitset<N>sum[N][N],summ[N][N]; void dfs(ll x,ll y,ll now,ll gg) {if(x>n||y>m){(ans+=g[gg])%=wyc;;return;}if(a[x][y]){if(summ[x-1][y][a[x][y]]||summ[x][y-1][a[x][y]]||sum[x+1][y][a[x][y]]||sum[x][y+1][a[x][y]])return;summ[x][y]=summ[x-1][y]|summ[x][y-1];summ[x][y].set(a[x][y],1);if(n-x+m-y>k-summ[x][y].count())return;dfs(x+y/m,y%m+1,now,gg);return;}for(ll i=1;i<=k;++i)if(p[i]||i<=now){if(summ[x-1][y][i]|| summ[x][y-1][i]||sum[x+1][y][i]||sum[x][y+1][i])continue;summ[x][y]=summ[x-1][y]|summ[x][y-1];summ[x][y].set(i,1);if(n-x+m-y>k-summ[x][y].count())return;if(i==now)dfs(x+y/m,y%m+1,nx[now],gg+1);else dfs(x+y/m,y%m+1,now,gg);}return; } int main() {scanf("%lld%lld%lld",&n,&m,&k);if(n+m-1>k){puts("0");return 0;}for(ll i=1;i<=n;++i)for(ll j=1;j<=m;++j)scanf("%lld",&a[i][j]);for(ll i=n;i>0;--i)for(ll j=m;j>0;--j)if(a[i][j]){sum[i][j]|=sum[i][j+1]|sum[i+1][j];if(sum[i][j][a[i][j]]){puts("0");return 0;}sum[i][j].set(a[i][j],1);p[a[i][j]]=1;}ls=k+1;for(ll i=k;i>0;--i)if(!p[i]){num++;nx[i]=ls;ls=i;}g[0]=1;for(int i=1;i<=num;++i)g[i]=g[i-1]*(num-i+1);dfs(1,1,ls,0);printf("%lld",ans);return 0; }

總結(jié)

以上是生活随笔為你收集整理的【dfs】飞行棋的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。