[蓝桥杯 2020 省 AB1] 走方格

题意

从 (1,1) 出发，只能向右或向下走到 (n,m)。

如果某个格子的行号和列号同时为偶数，就不能进入这个格子。

要求输出总方案数。

思路

这题就是最基础的网格路径计数 DP。

最直接的教学版做法是搜索所有路径：

cpp

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
31
32
33
34
35
36// brute.cpp：用搜索枚举所有向右/向下走法，作为教学版和对拍基准程序。
#include <bits/stdc++.h>
using namespace std;

int n, m;
long long ans;

bool blocked(int x, int y) {
    return x % 2 == 0 && y % 2 == 0;
}

void dfs(int x, int y) {
    if (x > n || y > m) {
        return;
    }
    if (blocked(x, y)) {
        return;
    }
    if (x == n && y == m) {
        ans++;
        return;
    }

    dfs(x + 1, y);
    dfs(x, y + 1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    dfs(1, 1);
    cout << ans << '\n';
    return 0;
}

但正式解法更直接：

设 dp[i][j] 表示走到 (i,j) 的方案数。

如果 (i,j) 是禁入格，dp[i][j] = 0
否则 dp[i][j] = dp[i-1][j] + dp[i][j-1]

起点 dp[1][1] = 1，最后答案就是 dp[n][m]。

DP 公式

设 $dp_{i,j}$ 表示从起点走到格子 $(i,j)$ 的方案数，禁入格集合为 $B$ 。初始化：

dp_{1,1}=1

转移为：

dp_{i,j}=\begin{cases} 0, & (i,j)\in B,\\ dp_{i-1,j}+dp_{i,j-1}, & (i,j)\notin B. \end{cases}

最终答案是：

dp_{n,m}

公式解释：走到 (i,j) 的最后一步只能来自上方或左方，所以方案数就是这两个来源相加。禁入格不能停留，状态直接为 0；起点有一种空路径，因此从 dp[1][1]=1 开始递推。

代码

cpp

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
31
32
33
34
35
36
37
38
39
40#include <bits/stdc++.h>
using namespace std;

const int MAXN = 35;

int n, m;
long long dp[MAXN][MAXN]; // dp[i][j] 表示走到 (i,j) 的方案数

bool blocked(int x, int y) {
    return x % 2 == 0 && y % 2 == 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    if (blocked(1, 1)) {
        cout << 0 << '\n';
        return 0;
    }

    dp[1][1] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (i == 1 && j == 1) {
                continue;
            }
            if (blocked(i, j)) {
                dp[i][j] = 0;
                continue;
            }
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }

    cout << dp[n][m] << '\n';
    return 0;
}

复杂度

时间复杂度： $O(nm)$
空间复杂度： $O(nm)$

总结

这题的变化只有一个：某些格子不能进。

把这些格子当作障碍，剩下就是标准二维 DP 模板题。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

[蓝桥杯 2020 省 AB1] 走方格

目录

题意

思路

DP 公式

代码

复杂度

总结

一图流解析