【题解】寻宝

题意

给你一个nxm的矩形你从(1,1)出发到(n,m)只能往上走和往右走，中间有一块矩形区域不能走矩形左下角是(x0,y0)，右上角是(x1,y1)，求一共有多少种方案，答案对1e9+7取模

题解

除去中间的陷阱区域可以把地图划分为这几块部分，我们先只看红色框的部分，假设两点之间的方案数的函数为f，那么从S出发到达T只经过红框部分的方案数就是，同理黄色框部分的方案数就是。也就是说对于给定的藏宝图，我们都可以将其划分为红框和黄框部分。即从x1+1遍历到n以及从y1+1遍历到m。那么再来看看f函数是什么，根据题意只能向上走或者向右走，这实际上是一个非降路径问题，若有从(0,0)出发到达(n,m)，一共会进行n次向右和m次向上，合在一起的选择次数是n+m，造成方案数不同的原因就是选择向上和向右的顺序不同，那么例如我们只看向右的选择，也就是说相当于从n+m中选出n个，即或者。题目中n和m的范围是1e3，这个范围我们可以用杨辉三角来预处理打表出组合数。因为涉及到了n+m，组合数数组的范围至少要2e3

时间复杂度

用杨辉三角预处理组合数复杂度为O(n^2)，后续处理答案就是两次O(n)遍历，当然组合数可以用阶乘逆元来优化时间可以降到O(n)，数据范围还可以扩大到1e6

代码

const int N=2e3+5;
const int mod=1e9+7;
long long C[N][N];
class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @param m int整型 
     * @param x0 int整型 
     * @param y0 int整型 
     * @param x1 int整型 
     * @param y1 int整型 
     * @return int整型
     */


    void get_C()
    {
        C[0][0] = 1;
        for(int i=1;i<N;i++)
        {
            C[i][0] = 1;
            for(int j=1;j<=i;j++)
                C[i][j] = (C[i-1][j]+C[i-1][j-1])%mod;
        }
    }
    long long f(int n,int m)
    {
        return C[n+m-2][n-1];
    }

    int GetNumberOfPath(int n, int m, int x0, int y0, int x1, int y1) {
        get_C();
        long long ans=0;
        for(int i=x1+1;i<=n;i++)
            ans=(ans+f(i,y0-1)*f(n-i+1,m-y0+1)%mod)%mod;
        for(int i=y1+1;i<=m;i++)
            ans=(ans+f(x0-1,i)*f(n-x0+1,m-i+1)%mod)%mod;
        return ans;
    }
};

解法二

可以利用dp来求解，若是正常的转移方程为dp[i][j]=d[i-1][j]+dp[i][j-1]，但是有了限定区域，所以我们只要在限定区域内continue就可以了

代码

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @param m int整型 
     * @param x0 int整型 
     * @param y0 int整型 
     * @param x1 int整型 
     * @param y1 int整型 
     * @return int整型
     */
    const int mod=1e9+7;
    int GetNumberOfPath(int n, int m, int x0, int y0, int x1, int y1) {
        // write code here
        int dp[m+5][n+5];
        memset(dp,0,sizeof(dp));
        dp[1][1]=1;
        for(int i=1; i<=m; i++)
            for(int j=1; j<=n; j++)
            {
                if(i==1&&j==1)
                    continue;
                if(i>=y0&&j>=x0&&i<=y1&&j<=x1)
                    continue;
                dp[i][j]=(dp[i-1][j]+dp[i][j-1])%mod;
            }
        return dp[m][n];
    }
};