工信部网站备案查询官网,做医药中间体的外贸网站,网站建设的行业动态,商标查询软件题目大意
给你一个n*m的网格#xff0c;现在让你往里面填1~k#xff08;有的位置已经填了#xff09;#xff0c;使其满足所有从(1,1)到(n,m)的路径不会经过相同的数字#xff08;只能往下或往右#xff09;#xff0c;求方案数 解题思路
对于knm-1的#xff0c;…题目大意
给你一个n*m的网格现在让你往里面填1~k有的位置已经填了使其满足所有从(1,1)到(n,m)的路径不会经过相同的数字只能往下或往右求方案数 解题思路
对于knm-1的无法填满任意一条路径特判掉
然后考虑dfs
每个位置只填左上矩阵和右下矩阵没填过的数保证不重且如果当前位置剩余颜色小于到终点的距离那么直接特判
对于自由填的颜色输入没填过考虑到某些方案只是将颜色转换了一下那么让自由填的颜色从小到大填然后乘排列数 code
#includebitset
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#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];
bitsetNsum[N][N],summ[N][N];
void dfs(ll x,ll y,ll now,ll gg)
{if(xn||ym){(ansg[gg])%wyc;;return;}if(a[x][y]){if(summ[x-1][y][a[x][y]]||summ[x][y-1][a[x][y]]||sum[x1][y][a[x][y]]||sum[x][y1][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-xm-yk-summ[x][y].count())return;dfs(xy/m,y%m1,now,gg);return;}for(ll i1;ik;i)if(p[i]||inow){if(summ[x-1][y][i]|| summ[x][y-1][i]||sum[x1][y][i]||sum[x][y1][i])continue;summ[x][y]summ[x-1][y]|summ[x][y-1];summ[x][y].set(i,1);if(n-xm-yk-summ[x][y].count())return;if(inow)dfs(xy/m,y%m1,nx[now],gg1);else dfs(xy/m,y%m1,now,gg);}return;
}
int main()
{scanf(%lld%lld%lld,n,m,k);if(nm-1k){puts(0);return 0;}for(ll i1;in;i)for(ll j1;jm;j)scanf(%lld,a[i][j]);for(ll in;i0;--i)for(ll jm;j0;--j)if(a[i][j]){sum[i][j]|sum[i][j1]|sum[i1][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;}lsk1;for(ll ik;i0;--i)if(!p[i]){num;nx[i]ls;lsi;}g[0]1;for(int i1;inum;i)g[i]g[i-1]*(num-i1);dfs(1,1,ls,0);printf(%lld,ans);return 0;
}
