Distinct Paths
题目链接：http://codeforces.com/problemset/problem/293/B
数据范围：略。
题解：
带搜索的剪枝....
想不到吧.....
但是剪枝也比较简单，就是能想到的剪枝都加上能过的那种搜索题。
代码：
#include <bits/stdc++.h>
#define setIO(s) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
using namespace std;
const int mod = 1000000007 ;
int Log[1100], n, m, k, a[21][21], f[21][21], v[21];
int dfs(int x, int y) {
if (y == m + 1) {
x ++ , y = 1;
}
if (x == n + 1) {
return 1;
}
int s = f[x - 1][y] | f[x][y - 1], calc = -1, re = 0;
int S = ~s & ((1 << k) - 1);
if (n + m - x - y + 1 > Log[S]) {
return 0;
}
for (int t = 0; t < k; t ++ ) {
if (S & (1 << t)) {
if (a[x][y] == 0 || a[x][y] == t + 1) {
v[t + 1] ++ ;
f[x][y] = s | (1 << t);
if (v[t + 1] == 1) {
if (calc == -1) {
calc = dfs(x, y + 1);
}
re += calc;
}
else {
re += dfs(x, y + 1);
}
if (re >= mod) {
re -= mod;
}
v[t + 1] -- ;
}
}
}
return re;
}
int main() {
// setIO("search&force");
for (int i = 1; i < 1024; i ++ ) {
Log[i] = Log[i >> 1] + (i & 1);
}
// int T;
// cin >> T ;
// while (T -- ) {
// memset(v, 0, sizeof v);
// memset(f, 0, sizeof f);
cin >> n >> m >> k ;
if (n + m - 1 > k) {
puts("0");
return 0;
}
for (int i = 1; i <= n; i ++ ) {
for (int j = 1; j <= m; j ++ ) {
scanf("%d", &a[i][j]);
v[a[i][j]] ++ ;
}
}
cout << dfs(1, 1) << endl ;
return 0;
}