题目

题目描述： 
赛时提示：保证出发点和终点都是空地
帕秋莉掌握了一种木属性魔法
这种魔法可以生成一片森林（类似于迷阵），但一次实验时，帕秋莉不小心将自己困入了森林
帕秋莉处于地图的左下角，出口在地图右上角，她只能够向上或者向右行走
现在给你森林的地图，保证可以到达出口，请问有多少种不同的方案
答案对2333取模

输入描述：
第一行两个整数m , n表示森林是m行n列
接下来m行，每行n个数，描述了地图
0  -  空地
1  -  树（无法通过）

输出描述：
一个整数表示答案

解析

这道题一看题型就能发现是dp。（我一开始还看成了是到终点的步数，我是瞎了吗）
  • 我们知道，dp的基本操作就是递推！

所以我们只要知道了递推公式就完美了。
  1. 因为这道题题目也告诉了我们，我们只能往上面和右边走。
  2. 这么说不就是在告诉我们：当前点的方法数=下面点的方法数+左边节点的方法数。
  3. 总结出来递推公式就是dp[i][j] = dp[i+1][j] + dp[i][j - 1]。

那么操作就是：
  1. 先初始化地图数组（mp数组）。
  2. 将第一行和第一列设置为1作为递推的根（因为单纯按行或按列走只有一种情况）。
    同时注意从起点向上和向右遇到了障碍就要停下来，因为我们没办法向下和左走，所以永远不可能到达。
  3. 然后从离起点最近的地方，一层一层的遍历完整个数组，我们就可以知道每个位置的可能数了。
  4. 最后把要的节点输出来就好了。

代码 

#include <iostream>
using namespace std;
const int MOD = 2333;
const int MAX = 3e3 + 7;
//代码预处理
int mp[MAX][MAX], dp[MAX][MAX];

inline void read(int& res);

int main() {
    int n, m; read(n); read(m);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            read(mp[i][j]);
        //初始化地图
    for (int i = n; i >= 1; i--)
        if (mp[i][1]) break;
        else dp[i][1] = 1;
    //第1列初始化
    for (int i = 1; i <= m; i++)
        if (mp[n][i]) break;
        else dp[n][i] = 1;
    //第n行初始化
    for (int i = n - 1; i >= 1; i--)
        for (int j = 2; j <= m; j++)
            if (mp[i][j]) dp[i][j] = 0;
            else dp[i][j] = (dp[i + 1][j] + dp[i][j - 1]) % MOD;
    //可能数=行可能数+列可能数
    cout << dp[1][m] << endl;
    return 0;
}

inline void read(int& res) {
    char c; int flag = 1;
    while ((c = getchar()) < '0' || c > '9') 
        if (c == '-') 
            flag = -1; 
    res = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        res = res * 10 + c - '0'; 
    res *= flag;
}