链接:

时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 131072K,其他语言262144K
64bit IO Format:%lld

题目描述

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

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

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

答案对2333取模

输入描述:

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

输出描述:

一个整数表示答案

示例1
输入

3 3
0 1 0
0 0 0
0 0 0

输出

3

题解:
经典的递推式,记忆化搜索
从左下角↙走到右上角↗
式子:
dp [ i] [ j ] = dp [ i - 1 ] [ j ] + d p [ i ] [ j - 1 ]
意义:当前这个点(i,j),是由他的左侧(i-1,j)和下侧(i,j-1)走到的
话说出题人真好,还提供了快读模板
代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=2333;
const int maxn=3004;
bool a[maxn][maxn];
ll dp[maxn][maxn];
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 main()
{
    int n,m;
    read(m);
    read(n);
    for(int i=1;i<=m;i++)
    for(int j=1;j<=n;j++)
    {
        read(a[i][j]);
        if(i==m&&j==1)dp[i][j]=1;
    }

    for(int i=m;i>=1;i--)
    for(int j=1;j<=n;j++)
    {
        if(a[i][j]==1)continue;
        else if(i!=n||j!=1)dp[i][j]=(dp[i+1][j]+dp[i][j-1])%mod;
    }
    cout<<dp[1][n];
    return 0;
}