链接: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
,
- 定义状态 : d p [ i ] [ j ] 表 示 到 格 子 ( i , j ) 有 多 少 种 路 径 dp[i][j]表示到格子(i,j)有多少种路径 dp[i][j]表示到格子(i,j)有多少种路径
- 转移方程 :
-
- 当 ( i , j ) (i,j) (i,j)
在
给定的障碍范围内时, d p [ i ] [ j ] = 0 dp[i][j]=0 dp[i][j]=0
- 当 ( i , j ) (i,j) (i,j)
-
- 不在障碍内, d p [ i ] [ j ] = m a x ( d p [ i ] [ j ] , d p [ i − 1 ] [ j ] + d p [ i ] [ j − ] ) dp[i][j]=max(dp[i][j],dp[i-1][j]+dp[i][j-]) dp[i][j]=max(dp[i][j],dp[i−1][j]+dp[i][j−])
- 边界 : 格子 ( 1 , 1 ) (1,1) (1,1)只有一种走法,所以 d p [ 1 ] [ 1 ] = 1 dp[1][1]=1 dp[1][1]=1,当然,如果 ( 1 , 1 ) (1,1) (1,1)在障碍范围内的话 d p [ 1 ] [ 1 ] 应 该 为 0 dp[1][1]应该为0 dp[1][1]应该为0
- 最后注意
mod
1e9+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 << "3[31;1m " << #x << " -> "; \ err(x); \ } while (0)
void err() { cout << "3[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