C题题解

蒟蒻实在太傻，只能写个C题题解呜呜呜~

这个题很明显是个动态规划，经典跳马问题。。

用f数组记录方案数。

所以蒟蒻不多解释啦，直接上代码：

int f[1002][1002];
bool can[1002][1002];
const int M=1000000007;
class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @param m int整型 
     * @param x0 int整型 
     * @param y0 int整型 
     * @param x1 int整型 
     * @param y1 int整型 
     * @return int整型
     */
    inline bool check(int xx,int bjn,int yy,int bjm){
        if(xx>0&&xx<=bjn&&yy>0&&yy<=bjm) return true;
        return false;
    }
    int GetNumberOfPath(int n, int m, int x0, int y0, int x1, int y1) {
        if(n==1&&m==1) return 0;
        memset(can,true,sizeof(can));
        for(int i=x0;i<=x1;++i)
            for(int j=y0;j<=y1;++j) can[i][j]=false;
        f[1][1]=1;
        for(int i=1;i<=n;++i){
            for(int j=1;j<=m;++j){
                if(i+j==2) continue;
                if(check(i-1,n,j,m)&&can[i-1][j]) f[i][j]+=f[i-1][j],f[i][j]%=M;
                if(check(i,n,j-1,m)&&can[i][j-1]) f[i][j]+=f[i][j-1],f[i][j]%=M;
            }
        }
        return f[n][m];
    }
};

PS:不点个赞再走？？