Codeforces 293B Distinct Paths

发现 \(n, m\) 的数据范围是假的，因为每一步一个颜色最多也就 \(k\le 10\) 种颜色，所以当 \(n + m - 1 > k\) 时一定无解。

接下来发现这个数据范围挺小的，考虑状压，设 \(f_{x, y}\) 为走到 \((x, y)\) 点所用的颜色的集合，其可以由 \(f_{x - 1, y}, f_{x, y - 1}\) 推来。
然后就可以枚举还未选过的颜色，选一个填到 \((x, y)\)，同时更新 \(f_{x, y}\)，因为多用了一个颜色，然后继续往后推一步步得到答案，推的顺序可以一行一行推。

这样朴素的搜索肯定是过不了的，考虑优化：

• 若 \(k - \operatorname{popcount}(f_{x, y})<(n - x) + (m - y) + 1\)（此时 \((x, y)\) 还没有选颜色，\(\operatorname{popcount(x)}\) 代表 \(x\) 二进制下 \(1\) 的个数），即剩余的颜色已经不足以继续填到终点，方案数肯定为 \(0\)。
• 若在同一方格的染色过程中，\(a, b\) 两种颜色都是第一次在图中出现，那么 \(a,b\) 对应的贡献一定是相同的，所以对于只需算出 \(a\) 的贡献 \(ret\)，\(b\) 的贡献也为 \(ret\) 不用再次计算。

// lhzawa(https://www.cnblogs.com/lhzawa/)
// Problem: B. Distinct Paths
// Contest: Codeforces - Croc Champ 2013 - Round 2
// URL: https://codeforces.com/problemset/problem/293/B
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int N = 10 + 5;
int n, m, k;
int col[N][N], f[N][N];
int ud[N];
const int mod = 1e9 + 7;
int dfs(int x, int y) {
	if (y > m) {
		x++, y = 1;
	}
	if (x > n) {
		return 1;
	}
	int s = f[x - 1][y] | f[x][y - 1];
	int cnt = k;
	for (int i = 1; i <= k; i++) {
		if ((s >> (i - 1)) & 1) {
			cnt--;
		}
	}
	if (cnt < (n - x) + (m - y) + 1) {
		return 0;
	}
	int ret = -1, ans = 0;
	for (int i = 1; i <= k; i++) {
		if ((col[x][y] && col[x][y] != i) || ((s >> (i - 1)) & 1)) {
			continue;
		}
		f[x][y] = s | (1 << (i - 1));
		if (! ud[i]) {
			ud[i] = 1;
			if (ret == -1) {
				ret = dfs(x, y + 1);
			}
			ans = (ans + ret) % mod;
			ud[i] = 0;
		}
		else {
			ans = (ans + dfs(x, y + 1)) % mod;
		}
	}
	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", &col[i][j]);
			ud[col[i][j]] = 1;
		}
	}
	printf("%d\n", dfs(1, 1));
	return 0;
}