链接：https://ac.nowcoder.com/acm/problem/53675

题目描述

赛时提示：保证出发点和终点都是空地

帕秋莉掌握了一种木属性魔法
这种魔法可以生成一片森林（类似于迷阵），但一次实验时，帕秋莉不小心将自己困入了森林
帕秋莉处于地图的左下角，出口在地图右上角，她只能够向上或者向右行走

现在给你森林的地图，保证可以到达出口，请问有多少种不同的方案

答案对2333取模

输入描述:

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

输出描述:

一个整数表示答案
示例1
输入
3 3
0 1 0
0 0 0
0 0 0
输出
3

思路：

本题是一道递推，与过河卒类似（https://ac.nowcoder.com/acm/problem/16708）。但是要注意递推方向。

#include<iostream>
#include<cmath>
#include<string.h>
#include<stdio.h>
using namespace std;

template<class T>inline void read(T &res)
{
char c;T 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;
}
int s[3005][3005];
int dp[3005][3005];
int main(){
    int n,m;
    read(n);
    read(m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            read(s[i][j]);    
        }
    }

    for(int i=n;i>=1;i--){
        for(int j=1;j<=m;j++){
            if(i==n&&j==1){
                dp[n][1]=1;//起点位置初始化为1 
            } 
            else if(s[i][j]==1){
                dp[i][j]=0;
                continue;
            }//如果地图上这个位置是1则不能到达?

            else{
                dp[i][j]=dp[i+1][j]+dp[i][j-1];
            }//如果不满足上面则到达这个点的路径数为左边加下面 
            dp[i][j]%=2333;
        }
    }
    cout<<dp[1][m]%2333;//输出到达终点路径数 
    return 0;
}