DP入门——迷宫行走方案2

题目描述

给你一个 (n) 行 (m) 列的二维迷宫，一开始你在迷宫的左上角的格子 ((1,1)) 处（我们用位置 ((x,y)) 来表示第 (x) 行第 (y) 列），你要走到右下角的格子 ((n,m)) 处，但是你是不能随便走的，
行走的方向是有规定的：每一步你只能往右移动一格，或者往下移动一个，并且你不能移动出迷宫的边界；
出了方向以外呢，我们还有另一个限制，在迷宫的每个格子里都有一个大写的英文字符 (c_{i,j}) （我们用 (c_{i,j}) 来表示格子 ((i,j)) 处的格子），对于两个格子 ((x1,y1)) 和 ((x2,y2)) ，如果 (c_{x1,y1} gt c_{x2,y2}) ，那么就算 ((x2,y2)) 是 ((x1,y1)) 右边的或者下边的格子，我们也不能从 ((x1,y1)) 移动到 ((x2,y2)) ，也就是说，你只能从一个ASCII较小的格子移动到它右边或上边那个ASCII较大的格子。
请问在这种限制下，你有多少种不同的移动方案。
说明：只要从起点到终点的移动路线不同，那么我们就说它们是不同的移动方案。比如：假设 (n = m = 2)，并且迷宫形状如样例输入一样的时候，从左上角 ((1,1)) 移动到右下角 ((2,2)) 共有(2) 种移动方案：

((1,1) Rightarrow (1,2) Rightarrow (2,2))
((1,1) Rightarrow (2,1) Rightarrow (2,2))

输入格式

输入一行包含两个整数 (n,m(1 le n,m le 10)) ，以空格分隔。
接下来n行每行包含一个长度为m的字符串，用于描述这个二维迷宫。

输出格式

输出包含一个整数，表示从 ((1,1)) 走到 ((n,m)) 的方案数。

样例输入

2 2
AB
CD

样例输出

本题涉及算法：动态规划。
本题和“迷宫行走方案1”类似，只不过多了一个限制。
我们设状态 (f[i][j]) 表示从 ((1,1)) 走到 ((i,j)) 的方案总数；
那么：

对于 ((1,1)) 来说，(f[1][1] = 1) ；
对于除了 ((1,1)) 以外的所有第 (1) 行的元素 ((1,i)) 来说，因为 ((1,i)) 只有可能是从 ((1,i-1)) 走过来的，所以:
1. 当 (c_{1,i-1} lt c_{1,i}) 时，(f[1][i] = f[1][i-1]) ;
2. 当 (c_{1,i-1} ge c_{1,i}) 时，(f[1][i] = 0)
对于除了 ((1,1)) 以外的所有第 (1) 列的元素 ((i,1)) 来说，因为 ((i,1)) 只有可能是从 ((i-1,1)) 走过来的，所以：
1. 当 (c_{i-1,1} lt c_{i,1}) 时， (f[i][1] = f[i-1][1]) ;
2. 当 (c_{i-1,1} ge c_{i,1}) 时， (f[i][1] = 0)
对于其他的所有点 ((i,j)) ，因为 ((i,j)) 只能从 ((i-1,j)) 和 ((i,j-1)) 两个点走过来，所以：
1. 当 (c_{i-1,j} lt c_{i,j}) 并且 (c_{i,j-1} lt c_{i,j}) 时 (f[i][j] = f[i-1][j] + f[i][j-1]) ；
2. 当 (c_{i-1,j} lt c_{i,j}) 并且 (c_{i,j-1} ge c_{i,j}) 时 (f[i][j] = f[i-1][j]) ；
3. 当 (c_{i-1,j} ge c_{i,j}) 并且 (c_{i,j-1} lt c_{i,j}) 时 (f[i][j] = f[i][j-1]) ；
4. 当 (c_{i-1,j} ge c_{i,j}) 并且 (c_{i,j-1} ge c_{i,j}) 时 (f[i][j] = 0)

我们可以按照这个思路递推得到 (f[n][m]) 就是我们的答案。
实现代码如下：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 11;
int n, m, f[11][11];
char c[12][12];
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++)
        scanf("%s", c[i]+1);
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= m; j ++) {
            if (i == 1 && j == 1) f[1][1] = 1;
            else f[i][j] =
                    ((c[i-1][j] < c[i][j]) ? f[i-1][j] : 0)
                +   ((c[i][j-1] < c[i][j]) ? f[i][j-1] : 0);
        }
    }
    cout << f[n][m] << endl;
    return 0;
}

注意：这里有两个点要注意的。
注意点1是：我对 (c) 数组的输入，是保证所有的字符从 (c[1][1]) 到 (c[n][m]) 的；
注意点2是：我在计算 (f[i][j]) 的时候才用了两个三目运算符来代替了繁琐的判断。请好好领会老师的代码中所蕴含的简洁的哲学。