【牛客编程巅峰赛S1第10场】寻宝

题目

牛牛得到了一份寻宝图，根据寻宝图的指示，牛牛在一个 $n\times m$ 的网格中，牛牛的位置在 $(1,1)$ ，宝藏的位置在 $(n,m)$ 。
由于寻宝需要按照特定规则，所以牛牛只能往上走或者往右走。
藏宝人为了让故意为难牛牛，在地图中设置了一块长方形的陷阱区域，陷阱左下坐标为 $(x0,y0)$ ，右上坐标为 $(x1,y1)$ ，牛牛要是碰到了陷阱可能会有生命危险。
牛牛能顺利找到宝藏有多少种不同的寻宝路径？

解题思路

动态规划

$dp[i][j]$ 表示顺利到达位置 $(i,j)$ 时的路径数目。
牛牛可以往上走或往右走，所以 $dp[i][j] = dp[i-1][j] + dp[i][j-1]$ 。
当然前提是位置 $(i,j)$ 不是位于陷阱区域。如果是的话， $dp[i][j] = 0$ 。
最后，返回 $dp[n][m]$ 作为答案。

C++代码

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