给定一个int[][] map(C++ 中为vector >)网格图,若map[i][j]为1则该点不是障碍点,否则为障碍点。另外给定int x,int y,表示网格的大小。现有一个机器人要从网格左上角走到右下角,只能走格点且只能向右或向下走。请返回机器人从(0,0)走到(x - 1,y - 1)有多少种走法。请将结果Mod 1000000007以防止溢出,并保证x和y均小于等于50。
给定一个int[][] map(C++ 中为vector >)网格图,若map[i][j]为1则该点不是障碍点,否则为障碍点。另外给定int x,int y,表示网格的大小。现有一个机器人要从网格左上角走到右下角,只能走格点且只能向右或向下走。请返回机器人从(0,0)走到(x - 1,y - 1)有多少种走法。请将结果Mod 1000000007以防止溢出,并保证x和y均小于等于50。
思路:动态规划递归式为dp[i][j]=dp[i-1][j]+dp[i][j-1] dp[i][j]表示从i到j有多少种走法 import java.util.*; public class Robot { public int countWays(int[][] map, int x, int y) { int[][] dp=new int[x][y]; for(int k=0;k<y;k++){//为第一行赋初值 if(map[0][k]==1){ dp[0][k]=1;//从起点开始向右走就只有一种走法 } else { dp[0][k]=0;//如果有障碍,则就无法到达,所以dp[0][k]=0,该行后边的自然也都无法到达 break; } } for(int k=0;k<x;k++){//为第一列赋初值 if(map[k][0]!=1) { dp[k][0]=0; break; } else dp[k][0]=1; } for(int i=1;i<x;i++){ for(int j=1;j<y;j++){ if(map[i][j]!=1) dp[i][j]=0;//要到达的点是障碍点则说明不可达。所以dp[i][j]=0 else dp[i][j]=(dp[i-1][j]+dp[i][j-1])%1000000007; } } return dp[x-1][y-1]; } }