机器人方格II

题目：

有一个XxY的网格，一个机器人只能走格点且只能向右或向下走，要从左上角走到右下角。请设计一个算法，计算机器人有多少种走法。注意这次的网格中有些障碍点是不能走的。

给定一个int[][] map(C++ 中为vector >),表示网格图，若map[i][j]为1则说明该点不是障碍点，否则则为障碍。另外给定int x,int y，表示网格的大小。请返回机器人从(0,0)走到(x - 1,y - 1)的走法数，为了防止溢出，请将结果Mod 1000000007。保证x和y均小于等于50

思路：

动态规划，不需要去考虑所依赖点是否是障碍点

因为就算是障碍点，那么值为0就行，这样就忽略解决了依赖点是障碍点的情况，还不用特判断

总结一下就是：

• 不能走，就是方法数==0
• 起点，1种走法
• 上边沿：只能从左边来
• 左边沿：只能从上边来
• 其他点：左边+上边

coding

class Robot:
    def countWays(self, m, x, y):
        # write code here
        mat = [[0 for i in range(y)] for j in range(x)]

        for row in range(x):
            for col in range(y):
                if m[row][col] == 0:
                    continue

                if row==0 and col==0:
                    mat[0][0] = 1
                elif row==0 and col != 0:
                    mat[row][col] = mat[row][col-1]
                elif row != 0 and col == 0:
                    mat[row][col] = mat[row-1][col]
                else:
                    mat[row][col] = (mat[row-1][col] + mat[row][col-1])%1000000007

        return mat[x-1][y-1]