「木」迷雾森林

题目

帕秋莉处于地图的左下角，出口在地图右上角，她只能够向上或者向右行走。
现在给出森林的地图，保证可以到达出口，请问有多少种不同的方案。答案对2333取模。
0 - 空地
1 - 树（无法通过）
保证出发点和终点都是空地。

解题思路

使用动态规划思想。
地图左下角的坐标为 (m-1,0)，右上角的坐标为 (0,n-1)。
dp[i][j] 表示从左下角到达坐标 (i,j) 的方案数目，dp[m-1][0] = 1。状态转移方程为
如果坐标 (i,j) 是树，dp[i][j] = 0；
如果坐标 (i,j) 是空地，dp[i][j] = dp[i+1][j] + dp[i][j-1]。
最终 dp[0][n-1] 即为所求。

C++代码

#include<cstdio>
#include<vector>
using namespace std;

const int mod = 2333;

int main(){
    int m, n;
    scanf("%d%d", &m, &n);
    vector<vector<char>> ground(m, vector<char>(n));
    char c = getchar();
    int i = 0;
    int j = 0;
    while(1){
        if(c=='0' || c=='1'){
            ground[i][j] = c;
            ++j;
            if(j==n){
                ++i;
                j = 0;
            }
        }
        if(i==m)
            break;
        c = getchar();
    }
    vector<vector<int>> dp(m, vector<int>(n,0));
    dp[m-1][0] = 1;
    for(int i=m-1; i>=0; --i){
        for(int j=0; j<n; ++j){
            if(ground[i][j]=='0'){
                if(i<m-1)
                    dp[i][j] = dp[i+1][j];
                if(j>0)
                    dp[i][j] += dp[i][j-1];
            }
            dp[i][j] %= mod;
        }
    }
    printf("%d\n", dp[0][n-1]);
    return 0;
}