首页 > 试题广场 >

简单变向

[编程题]简单变向

热度指数：2321 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

牛牛准备在一个3行n列的跑道上跑步。一开始牛牛位于(1,1)。

当牛牛位于第i行第j列时，他可以的下一步最多可能有三种选择：

1. 跑到第i行第j+1列
2. 跑到第i-1行第j+1列（如果i=1则不可以这么跑）。
3. 跑到第i+1行第j+1列（如果i=3则不可以这么跑）。

跑道上有一些格子设置了路障(一个格子可能有多个路障)，牛牛不能跑到路障上。现在牛牛想知道，从(1,1)到(3,n)有多少条不同的路径？

为了防止答案过大，答案对1e9+7取模。

示例1

输入

4,1,[1],[2]

输出

说明

在第一行第二列的位置有一个障碍
牛牛有两种跑法：
1.  (1,1)->(2,2)->(2,3)->(3,4)
2.  (1,1)->(2,2)->(3,3)->(3,4)

备注:

，数据保证(1,1)和(3,n)上没有路障。
第一个参数n代表列数
第二个参数m代表路障个数
第三个参数和第四个参数x, y都包含m个元素，分别代表路障的行坐标和列坐标。
同一个格子可能有多个路障。

算法知识视频讲解

Java

牛客835606966号

public static int solve (int n, int m, int[] x, int[] y) {
// write code here
int[][] dp = new int[3][n];
dp[0][0] = 1;
int mod = 1000000007;
//初始化，路障不可达
for(int i = 0; i < m; i++){
    dp[x[i]-1][y[i]-1] = -1;
}
for(int j = 1; j < n; j++) {
    for(int i = 0; i < 3; i++) {
        if (dp[i][j] == -1) {
                    continue;
                }
        if (i == 0) {
                    dp[i][j] = (Math.max(0, dp[i][j-1])%mod+Math.max(0, dp[i+1][j-1])%mod)%mod;

}else if(i == 1){

//根据取模公式(x+y)⊙p = (x⊙p+y⊙p)⊙p，但是不可扩展为同形式的三个数的公式

dp[i][j] = (Math.max(0,dp[i-1][j-1])%mod+Math.max(0,dp[i][j-1]))%mod;
dp[i][j] = (dp[i][j]%mod+Math.max(0, dp[i+1][j-1])%mod)%mod;
}else{
dp[i][j] = (Math.max(0,dp[i-1][j-1])%mod+Math.max(0,dp[i][j-1])%mod)%mod;
}
}
}
return dp[2][n-1];
}

发表于 2020-08-06 15:31:19 回复(0)