【2022年11月15日提高A组】路径计数【DP】

思路：

直接DP

$code$

#include
#include

using namespace std;

const int MAXN = 3e3 + 10, mod = 1e9 + 7;

int n, m, t;
int v[MAXN][MAXN], f[MAXN][MAXN];

int main() {
	scanf("%d%d%d", &n, &m, &t);
	for(int i = 1; i <= t; i ++) {
		int a, b, c, d;
		scanf("%d%d%d%d", &a, &b, &c, &d);
		if(a + 1 == c && b == d) v[a][b] = (!v[a][b] || v[a][b] == 1) ? 1 : -1;
		else if(a == c && b + 1 == d) v[a][b] = (!v[a][b] || v[a][b] == 2) ? 2 : -1;
		else v[a][b] = -1;
	}
	f[1][1] = 1;
	for(int i = 1; i <= n; i ++)
		for(int j = 1; j <= m; j ++) {
			if(v[i][j] == -1) continue;
			if(v[i][j] == 1) f[i + 1][j] = (f[i + 1][j] + f[i][j]) % mod;
			else if(v[i][j] == 2) f[i][j + 1] = (f[i][j + 1] + f[i][j]) % mod;
			else  f[i + 1][j] = (f[i + 1][j] + f[i][j]) % mod, f[i][j + 1] = (f[i][j + 1] + f[i][j]) % mod;
		}
	printf("%d", f[n][m]);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30