题解 | #迷雾森林#

1010 【木】迷雾森林 看别人都在写递推，我就写个记忆化搜索吧，因为比较简单，所以直接上代码（）

需要注意的是，给dis赋值为-INF做初始值时，会出问题，大家可以自己试试

#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) ((x)&-x)
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const ll INF = 0x3f3f3f3f3f3f3f3fLL;
int m,n;
const int mod = 2333;
int mp[3001][3001]={0};
ll dis[3001][3001]={0};
ll go(int x,int y){
    if(x==m+1) return 0;
    if(y==0) return 0; 
    if(dis[x][y]!=-1) return dis[x][y];
    dis[x][y]=go(x,y-1)+go(x+1,y);
    dis[x][y]%=mod;
    return dis[x][y];
}
void solve(){
    cin>>m>>n;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++) cin>>mp[i][j];
    }
    memset(dis,-1,sizeof(dis));
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            if(mp[i][j]==1) dis[i][j]=0;
        }
    }
    dis[m][1]=1;
    cout<<go(1,n)<<"\n";
}
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    solve();
    return 0;
}