[Algorithm Elementary]迷雾森林

Thinking Process

初始点是(m,1)，终点是(1,n)。终点的最后一个状态只能从(1,n-1)或者(2,n)这两个坐标得来。对(i,j)这个坐标来说，由于题目只允许向上或者是向下走，所以f[i][j]=f[i][j-1]+f[i+1][j]。状态方程自然得到。

NOTICE

1. 此题不可以使用递归来做。会超时
2. 数组方面要开大一点，m和n都是3000的数据范围
3. 得开long long
4. 得取余 【一开始做的时候没取余搞得结果错了】

Code

#include<iostream>
using namespace std;
typedef long long ll;
int m, n;
int map[3010][3010];
int vis[3010][3010];
ll f[3010][3010];

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;
}

ll calc(int i, int j){
    if(i < 1 || j < 1 || map[i][j] == 1 || i > m || j > n) return 0;
    if(f[i][j]) return f[i][j];
    return f[i][j] = (calc(i, j - 1) + calc(i + 1, j)) % 2333;
}

int main() {
    read(m), read(n);
    for(int i = 1; i <= m;i ++ ) {
        for(int j = 1;j <= n; j ++ ) {
            read(map[i][j]);
        }
    }
    f[m][1] = 1;
    for(int i = m; i >= 1; i --) {
        for(int j = 1; j <= n; j ++) {
            if(i < 1 || j < 1 || map[i][j] == 1 || i > m || j > n) f[i][j] = 0;
            if(map[i][j - 1] != 1) f[i][j] += f[i][j - 1];
            if(map[i + 1][j] != 1) f[i][j] += f[i + 1][j];
            f[i][j] %= 2333;
        }
    }
    cout << f[1][n];
}