题解 | #「木」迷雾森林#

题目考点：dp

• 题目大意：左下到右上的走法数量，遇到1不走，走到该位置无效（注意快读和取模）

• 题目分析：过河卒的改版，不过是走的方向变了，思路还是一样的：走到该点的路径条数为左边点条数+下边点的路径条数，状态转移方程：mp[i][j] = mp[i+1][j] + mp[i][j-1]

• 特判：mp[n][1] = 1，即走到起点的路径数为1

#include<iostream>
#include<algorithm>

using namespace std;
typedef long long LL;

const int N = 3010, mod = 2333;
int n, m;
LL  mp[N][N];

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()
{
    read(n);
    read(m);

    for(int i = 1; i <= n; i++)
    for(int j = 1; j <= m; j++){
        read(mp[i][j]);
        if(mp[i][j])mp[i][j] = -1;
    }
    mp[n][1] = 1;

    for(int i = n; i >= 0; i--)
    for(int j = 1; j <= m; j++){
        if(mp[i][j] != -1)
        {
            if(mp[i+1][j] != -1) mp[i][j] += mp[i+1][j] % 2333;
            if(mp[i][j-1] != -1) mp[i][j] += mp[i][j-1] % 2333;
        }
    }
    printf("%lld", mp[1][m] % 2333);

    return 0;
}