欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  互联网

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

程序员文章站 2022-03-23 09:11:41
链接:https://ac.nowcoder.com/acm/contest/6909/C来源:牛客网题目描述牛牛得到了一份寻宝图,根据寻宝图的指示,牛牛在一个nxm的网格中,牛牛的位置在(1,1),宝藏的位置在(n,m),由于寻宝需要按照特定规则,所以牛牛只能往上走或者往右走。藏宝人为了让故意为难牛牛,在地图中设置了一块长方形的陷阱区域,牛牛要是碰到了陷阱可能会有生命危险,陷阱左下坐标为(x0,y0),右上坐标为(x1,y1)。为了牛牛能顺利找到宝藏你能告诉他有多少种不同的寻宝路径吗。示例1输...

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

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

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

示例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)dp[i][j]表示到格子(i,j)有多少种路径
  • 转移方程 :
    • (i,j)(i,j)给定的障碍范围内时,dp[i][j]=0dp[i][j]=0
    • 不在障碍内,dp[i][j]=max(dp[i][j],dp[i1][j]+dp[i][j])dp[i][j]=max(dp[i][j],dp[i-1][j]+dp[i][j-])
  • 边界 : 格子(1,1)(1,1)只有一种走法,所以dp[1][1]=1dp[1][1]=1,当然,如果(1,1)(1,1)在障碍范围内的话dp[1][1]0dp[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