Advertisement

牛客网上的一个动态规划练习题：机器人走方格问题

阅读量：

题目描述：
给定一个int[][] map（在C++中表示为vector<vector>）的网格图，在map[i][j]为1的位置表示该点是障碍点；其余位置则不是障碍点。另外给定整数x和y表示网格的尺寸（即宽度和高度）。现在要求从网格左上角（起点为(0, 0)）走到右下角（终点为(x - 1, y - 1)）有多少种走法？其中机器人只能向右或向下移动经过格点。请将计算结果对1e9+7取模以避免数值溢出，并保证x和y均不超过50。

解析：
这道题与机器人走方格的主要区别在于多了一个障碍物的存在。因此，在状态转移方程上并未发生任何变化，在判断时只需确定是否存在障碍即可。

复制代码 
    class Robot {
    public:
    int countWays(vector<vector<int> > map, int x, int y) {
        // write code here
        int dp[51][51] = {0};
        for(auto i = 0; i < y; i++)
        {
            if(map[0][i] != 1)break;
            dp[0][i] = 1;
        }
        for(auto j = 0; j < x; j

全部评论 (0)

还没有任何评论哟~

相关文章推荐