有一个XxY的网格,一个机器人只能走格点且只能向右或向下走,要从左上角走到右下角。请设计一个算法,计算机器人有多少种走法。注意这次的网格中有些障碍点是不能走的。
给定一个int[][] map(C++ 中为vector >),表示网格图,若map[i][j]为1则说明该点不是障碍点,否则则为障碍。另外给定int x,int y,表示网格的大小。请返回机器人从(0,0)走到(x - 1,y - 1)的走法数,为了防止溢出,请将结果Mod 1000000007。保证x和y均小于等于50
int
countWays(vector<vector<
int
> > map,
int
x,
int
y) {
vector<vector<
int
> > f(x,vector<
int
>(y,0));
for
(
int
i=0;i<x;i++)
for
(
int
j=0;j<y;j++)
{
if
(map[i][j] != 1)f[i][j] = 0;
// 不能走,就是方法数==0
else
if
(i==0 && j==0)f[i][j] = 1;
// 起点,1种走法
else
if
(i==0 && j!=0)f[i][j] = f[i][j-1];
// 上边沿:只能从左边来
else
if
(i!=0 && j==0)f[i][j] = f[i-1][j];
// 左边沿:只能从上边来
else
f[i][j] = (f[i-1][j]+f[i][j-1]) % 1000000007;
其他:左边+上边
}
return
f[x-1][y-1];
}
联系客服