首页 > 试题广场 >

简单变向

[编程题]简单变向
  • 热度指数：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]

输出

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个元素，分别代表路障的行坐标和列坐标。
同一个格子可能有多个路障。
算法知识视频讲解
添加回答
C/C++
nbgao头像 nbgao 
class Solution {
public:
    /**
     * 简单变相
     * @param n int整型 
     * @param m int整型 
     * @param x int整型vector 
     * @param y int整型vector 
     * @return int整型
     */
    int solve(int n, int m, vector<int>& x, vector<int>& y) {
        bool a[4][n+1];
        long dp[4][n+1], M=1000000007;
        memset(a, false, sizeof(a));
        memset(dp, 0, sizeof(dp));
        dp[1][1] = 1;
        for(int i=0;i<m;i++)
            a[x[i]][y[i]] = true;
        for(int i=1;i<n;i++){
            if(!a[1][i+1])
                dp[1][i+1] = (dp[1][i] + dp[2][i])%M;
            if(!a[2][i+1])
                dp[2][i+1] = (dp[1][i] + dp[2][i] + dp[3][i])%M;
            if(!a[3][i+1])
                dp[3][i+1] = (dp[2][i] + dp[3][i])%M;
        }
        return dp[3][n]%M;
    }
};

发表于 2020-06-23 01:00:23 回复(0)
Resolmi头像 Resolmi
注意溢出就行了 
public int solve (int n, int m, int[] x, int[] y) {
    long[][] dp = new long[3][n+1];
    int MOD = (int)1e9+7;
    boolean[][] v = new boolean[3][n];
    for(int i = 0; i < m; i++){
        v[x[i]-1][y[i]-1] = true;
    }
    dp[0][0] = 1;
    for (int j = 1; j < n; j++) {
        dp[0][j] = v[0][j] ? 0 : (dp[0][j-1] + dp[1][j-1])%MOD;
        dp[1][j] = v[1][j] ? 0 : (dp[1][j-1] + dp[0][j-1]+dp[2][j-1])%MOD;
        dp[2][j] = v[2][j] ? 0 : (dp[2][j-1] + dp[1][j-1])%MOD;
    }
    return  (int)(dp[2][n-1]%MOD);
}



发表于 2020-08-31 18:29:59 回复(0)
復活の検事头像 復活の検事 
import java.util.*;


public class Solution {
    /**
     * 简单变相
     * @param n int整型
     * @param m int整型
     * @param x int整型一维数组
     * @param y int整型一维数组
     * @return int整型
     */
    public int solve (int n, int m, int[] x, int[] y) {
        int mod = 1000000007;
        int[][] dp = new int [4][n+1];
        dp[1][2] = 1;
        dp[2][2] = 1;
        dp[3][2] = -1;

        for(int i=0;i<x.length;i++){
            dp[x[i]][y[i]] = -1;
        }

        for(int j=3;j<=n;j++){
            int canA = dp[1][j-1] == -1 ? 0 : 1;
            int canB = dp[2][j-1] == -1 ? 0 : 1;
            int canC = dp[3][j-1] == -1 ? 0 : 1;

            int isA = dp[1][j] == -1 ? 0 : 1;
            int isB = dp[2][j] == -1 ? 0 : 1;
            int isC = dp[3][j] == -1 ? 0 : 1;

            dp[1][j] = (canA * dp[1][j-1] + canB * dp[2][j-1]) * isA % mod;
            dp[2][j] = ((canB * dp[2][j-1] + canA * dp[1][j-1]) % mod + canC * dp[3][j-1]) * isB % mod;
            dp[3][j] = (canC * dp[3][j-1] + canB * dp[2][j-1]) * isC % mod;
        }

        return dp[3][n];
    }
}

发表于 2020-08-10 20:38:38 回复(0)
Java
牛客835606966号头像 牛客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)
钢琴手1720头像 钢琴手1720
整型溢出!
3*(1e9 +7)= 3000000021> 2147483647
所以用unsigned int刚刚好，不过当然用long更稳健啦 
class Solution {
public:
    const int MOD=1e9+7;
    int solve(int n, int m, vector<int>& x, vector<int>& y) {
        // write code here
        vector<vector<int> > dp(4,vector<int>(n+1,0));
        for(int i=0;i<m;i++)
            dp[x[i]][y[i]]=-1;
        dp[1][1]=1;
        for(int i=2;i<=n;i++){
            unsigned int one = dp[1][i-1]==-1?0:dp[1][i-1];
            unsigned int two = dp[2][i-1]==-1?0:dp[2][i-1];
            unsigned int three = dp[3][i-1]==-1?0:dp[3][i-1];
            if(dp[1][i]!=-1)
                dp[1][i]=(one+two)%MOD;
            if(dp[2][i]!=-1)
                dp[2][i]=(one+two+three)%MOD;
            if(dp[3][i]!=-1)
                dp[3][i]=(two+three)%MOD;
        }
        return dp[3][n];
    }
};


发表于 2020-07-28 17:29:01 回复(0)
Python
落叶阳光头像 落叶阳光 
#
# 简单变相
# @param n int整型 
# @param m int整型 
# @param x int整型一维数组 
# @param y int整型一维数组 
# @return int整型
#
class Solution:
    def solve(self , n , m , x , y ):
        # write code here
        if not x&nbs***bsp;not y:
            return 0
        
        dep = [[0 for i in range(n + 1)] for i in range(3 + 1)]
        dep[1][1] = 1
        # 添加障碍标记,标记为-1
        for i in range(len(x)):
            dep[x[i]][y[i]] = -1
        
        for j in range(2, n+1):
            # 在计算之前，先判断是否为路障
            if dep[1][j] != -1:
                dep[1][j] += (dep[1][j-1] if dep[1][j-1] != -1 else 0)
                dep[1][j] += (dep[2][j-1] if dep[2][j-1] != -1 else 0)

            if dep[2][j] != -1:
                dep[2][j] += (dep[1][j-1] if dep[1][j-1] != -1 else 0)
                dep[2][j] += (dep[2][j-1] if dep[2][j-1] != -1 else 0)
                dep[2][j] += (dep[3][j-1] if dep[3][j-1] != -1 else 0)

            if dep[3][j] != -1:
                dep[3][j] += (dep[2][j-1] if dep[2][j-1] != -1 else 0)
                dep[3][j] += (dep[3][j-1] if dep[3][j-1] != -1 else 0)

        return dep[3][n] % (1000000007)


编辑于 2020-06-04 15:42:54 回复(0)
henry_dai头像 henry_dai 
class Solution {
public:
    /**
     * 简单变相
     * @param n int整型
     * @param m int整型
     * @param x int整型vector
     * @param y int整型vector
     * @return int整型
     */
    int solve(int n, int m, vector<int>& x, vector<int>& y) 
    {
        if (n == 1)  //第一列直接返回0;
            return 0;
        long** p = new long*[3];          //需要用long存,int范围不够
        for (int i = 0; i < 3; ++i)
        {
            p[i] = new long[n];
        }
        for (int i = 0; i < 3; ++i)
            for (int j = 0; j < n; ++j)
                p[i][j] = 0;

        for (int i = 0; i < m; ++i)
        {
            p[x[i]-1][y[i]-1] = -1;   //障碍设置为-1
        }

        p[0][0] = 1;   //起始位置设为1
        p[1][0] = 0;   //第一列其他位置设为0
        p[2][0] = 0;

        for(int j=1;j<n;++j)  //col,从第二列开始
            for (int i = 0; i < 3; ++i)  //row
            {
                if (p[i][j] != -1)  //非障碍点
                {
                    if (i == 0)        //第一行的点
                    {
                        p[i][j - 1] != -1 ? p[i][j] += p[i][j - 1] : p[i][j];
                        p[i + 1][j - 1] != -1 ? p[i][j] += p[i + 1][j - 1] : p[i][j];

                    }
                    else if (i == 1)
                    {
                        p[i - 1][j - 1] != -1 ? p[i][j] += p[i - 1][j - 1] : p[i][j];
                        p[i][j - 1] != -1 ? p[i][j] += p[i][j - 1] : 1;
                        p[i + 1][j - 1] != -1 ? p[i][j] += p[i + 1][j - 1] : p[i][j];
                    }
                    else if (i == 2)
                    {
                        p[i - 1][j - 1] != -1 ? p[i][j] += p[i - 1][j - 1] : p[i][j];
                        p[i][j - 1] != -1 ? p[i][j] += p[i][j - 1] : p[i][j];
                    }
                    p[i][j] %= 1000000007;
                }
            }
        

        return p[2][n - 1];
    }
};

发表于 2020-04-25 15:18:34 回复(1)
铁离子头像 铁离子 
int solve(int n, int m, vector<int>& x, vector<int>& y) {
	int mod = 1e9+7;
    vector<vector<long> >dp(3,vector<long>(n+1,0));
    dp[0][2] = 1;
    dp[1][2] = 1;
    for(int i=0;i<m;i++){
    	dp[x[i]-1][y[i]]=-1;
	}
	for(int j=3;j<=n;j++){
		if(dp[0][j-1]>=0){
			dp[0][j] = dp[0][j]>=0?(dp[0][j]+dp[0][j-1])%mod:-1;
			dp[1][j] = dp[1][j]>=0?(dp[1][j]+dp[0][j-1])%mod:-1;
		}
		if(dp[1][j-1]>=0){
			dp[0][j] = dp[0][j]>=0?(dp[0][j]+dp[1][j-1])%mod:-1;
			dp[1][j] = dp[1][j]>=0?(dp[1][j]+dp[1][j-1])%mod:-1;
			dp[2][j] = dp[2][j]>=0?(dp[2][j]+dp[1][j-1])%mod:-1;
		}
		if(dp[2][j-1]>=0){
			dp[1][j] = dp[1][j]>=0?(dp[1][j]+dp[2][j-1])%mod:-1;
			dp[2][j] = dp[2][j]>=0?(dp[2][j]+dp[2][j-1])%mod:-1;
		}
	}
	return dp[2][n];
}

发表于 2020-04-17 12:46:49 回复(0)
提交观点

问题信息

动态规划
难度：
8条回答 2085浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号