牛客编程巅峰赛S1第10场 - 黄金&钻石 c 寻宝 基础动态规划

链接：https://ac.nowcoder.com/acm/contest/6909/C
来源：牛客网

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

示例1
输入
复制

4,4,2,2,3,3

输出
复制

2

说明

只有两条可达路径

备注:

1≤n,m≤1031\leq n,m \leq 10^31≤n,m≤103，1≤x0≤x1≤n1\leq x0\leq x1\leq n1≤x0≤x1≤n，1≤y0≤y1≤m1\leq y0\leq y1\leq m1≤y0≤y1≤m , 答案可能很大请对1000000007取模

---

很基础的DP,

• 定义状态 : $dp[i][j]表示到格子(i,j)有多少种路径$
• 转移方程 :
• • 当$(i,j)$在给定的障碍范围内时,$dp[i][j]=0$
• • 不在障碍内,$dp[i][j]=max(dp[i][j],dp[i-1][j]+dp[i][j-])$
• 边界 : 格子$(1,1)$只有一种走法,所以$dp[1][1]=1$,当然,如果$(1,1)$在障碍范围内的话$dp[1][1]应该为0$
• 最后注意mod1e9+7

#define debug
#ifdef debug
#include <time.h>
#include "/home/majiao/mb.h"
#endif


#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <map>
#include <set>
#include <stack>
#include <queue>
#define MAXN ((int)1e5+7)
#define ll long long int
#define QAQ (0)

using namespace std;

#define num(x) (x-'0')

#define show(x...)                             \
    do {                                       \
        cout << "\033[31;1m " << #x << " -> "; \
        err(x);                                \
    } while (0)

void err() { cout << "\033[39;0m" << endl; }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }

//如果不在矩形(x0y0, x1y1)范围内就返回真
inline bool NOTIN(int x, int y, int x0, int y0, int x1, int y1) {
	return !(x>=x0 && x<=x1 && y>=y0 && y<=y1);
}

#define MOD (1000000007)

class Solution {
public:
    /**
     * @param n int整型 
     * @param m int整型 
     * @param x0 int整型 
     * @param y0 int整型 
     * @param x1 int整型 
     * @param y1 int整型 
     * @return int整型
     */
	int dp[1024][1024];
    int GetNumberOfPath(int n, int m, int x0, int y0, int x1, int y1) {
		memset(dp, false, sizeof(dp));
		for(int i=1; i<=m; i++)
			if(NOTIN(1, i, x0, y0, x1, y1)) { //初始化第1行每一列
				dp[1][i] = i==1 ? 1 : dp[1][i-1];
			}
		for(int i=1; i<=n; i++)
			if(NOTIN(i, 1, x0, y0, x1, y1)) { //初始化第1列每一行
				dp[i][1] = i==1 ? 1 : dp[i-1][1];
			}
		for(int i=1; i<=n; i++) {
			for(int j=1; j<=m; j++) {
				//所有在障碍范围内的格子都无法走到,则为0
				if(!NOTIN(i, j, x0, y0, x1, y1)) continue ;
				dp[i][j] = max(dp[i][j], dp[i-1][j]+dp[i][j-1]);
				dp[i][j] %= MOD;
//				printf("%d ", dp[i][j]);
			}
//			printf("\n");
		}
		return dp[n][m];
    }
};

#ifdef debug
signed main() {
	freopen("test", "r", stdin);
	clock_t stime = clock();

	Solution s;
	cout << s.GetNumberOfPath( 4, 4, 2, 2, 3, 3 ) << endl;







	clock_t etime = clock();
	printf("rum time: %lf 秒\n",(double) (etime-stime)/CLOCKS_PER_SEC);
	return 0;
}
#endif

本文地址：https://blog.csdn.net/qq_31036127/article/details/107890492