首页 > 试题广场 >

机器人走方格II

[编程题]机器人走方格II

热度指数：19247 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定一个int[][] map(C++ 中为vector >)网格图，若map[i][j]为1则该点不是障碍点，否则为障碍点。另外给定int x,int y，表示网格的大小。现有一个机器人要从网格左上角走到右下角，只能走格点且只能向右或向下走。请返回机器人从(0,0)走到(x - 1,y - 1)有多少种走法。请将结果Mod 1000000007以防止溢出，并保证x和y均小于等于50。

算法知识视频讲解

Python

你回家了我在等你呢

# -*- coding:utf-8 -*-
class Robot:
def countWays(self, m, x, y):
# write code here
tmparray=[[0]*(y+1) for _ in range(x+1)]
for i in range(1,x+1):
for j in range(1,y+1):
if m[i-1][j-1]!=0:
tmparray[i][j]=tmparray[i-1][j]+tmparray[i][j-1] if ((j!=1) or (i!=1)) else 1
return tmparray[x][y]

发表于 2019-05-29 12:16:21 回复(0)

Python

华科平凡

python solution

# -*- coding:utf-8 -*-
class Robot:
    def countWays(self, m, x, y):
        if m[-1][-1]==0:return 0
        for i in range(x-1,-1,-1):
            if m[i][-1]==1:
                m[i][-1]==1
            else:
                for j in range(i,-1,-1):
                    m[j][-1]=0
                break
        for i in range(y-2,-1,-1):
            if m[-1][i]==1:
                m[-1][i]=1
            else:
                for j in range(i,-1,-1):
                    m[-1][j]=0
        for i in range(x-2,-1,-1):
            for j in range(y-2,-1,-1):
                if m[i][j]==1:
                    m[i][j]=m[i+1][j]+m[i][j+1]
                else:
                    m[i][j]=0
        return m[0][0]

发表于 2017-10-31 18:02:51 回复(0)

Python

Yannyezixin

思路：

动态规划

dp[i][j] 表示起点到(i, j) 有多少条路径

起点到(i, j) 的路径等于起点到 (i - 1, j) 的路径加上起点到 (i, j - 1)的路径

即 dp[i][j] = dp[i - 1][j] + dp[i][j]

# -*- coding:utf-8 -*-
class Robot:
    def countWays(self, m, x, y):
        if not m or len(m) != x or len(m[0]) != y:
            return 0
        if m[x - 1][y - 1] != 1 or m[0][0] != 1:
            return 0
        
        dp = [[0] * y for i in xrange(x)]
        dp[0][0] = 1
        
        for i in xrange(1, x):
            if m[i][0] == 1:
                dp[i][0] = dp[i - 1][0]
        for j in xrange(1, y):
            if m[0][j] == 1:
                dp[0][j] = dp[0][j - 1]
                
        for i in xrange(1, x):
            for j in xrange(1, y):
                if m[i][j] == 1:
                    dp[i][j] = dp[i - 1][j] % 1000000007 + dp[i][j - 1] % 1000000007
                    
        return dp[x-1][y -1] % 1000000007

发表于 2016-08-04 20:40:46 回复(0)