Distinct Paths

代码

#include<cstdio>

using namespace std;

const int N = 20 , mod = 1e9 + 7 , K = 10;

int f[N + 5][N + 5] , map[N + 5][N + 5] , vis[K + 5] , n , m , k;

inline int dfs(int x , int y)

{

	if (y == m + 1) return dfs(x + 1 , 1);

	if (x == n + 1) return 1;

	f[x][y] = f[x - 1][y] | f[x][y - 1];

	int num = 0 , sum = 0 , res = 0 , bz = 0;

	for(register int i = 1; i <= k; i++)

	if (!(f[x][y] & (1 << i - 1))) num++;

	if (num < n + m - x - y + 1) return 0;

	if (!map[x][y])

	{

		for(register int i = 1; i <= k; i++)

		if (!(f[x][y] & (1 << i - 1)))

		{

			if (!vis[i])

			{

				if (bz == 1)

				{

					res = (res + sum) % mod;

					continue;

				}

				else

				{

					bz = 1;

					vis[i]++;

					f[x][y] |= 1 << i - 1;

					sum = dfs(x , y + 1);

					res = (res + sum) % mod;

					f[x][y] ^= 1 << i - 1;

					vis[i]--;

				}

				continue;

			}

			vis[i]++;

			f[x][y] |= 1 << i - 1;

			res = (res + dfs(x , y + 1)) % mod;

			f[x][y] ^= 1 << i - 1;

			vis[i]--;

		}

	}

	else if (!(f[x][y] & (1 << map[x][y] - 1)))

	{

		f[x][y] |= 1 << map[x][y] - 1;

		res = (res + dfs(x , y + 1)) % mod;

		f[x][y] ^= 1 << map[x][y] - 1;

	}

	return res;

}

int main()

{

	scanf("%d%d%d" , &n , &m , &k);

	if (n + m - 1 > k)

	{

		printf("0");

		return 0;

	}

	for(register int i = 1; i <= n; i++)

		for(register int j = 1; j <= m; j++)

		{

			scanf("%d" , &map[i][j]);

			vis[map[i][j]]++;

		}

	printf("%d" , dfs(1 , 1));

}
巴特西

Distinct Paths

代码

最新文章

热门文章
