这道题是对于机器人走方格I的升级版。
先说一下机器人Ⅰ:
1的情况比较简单,直接递归或者dp就可以求解:
int countWays(int x, int y) {//二维的上台阶问题 if((x==1||y==1))return 1; //只要到达1的旁边就返回1,相当于直接把左边界和上边界跳过了 return countWays(x-1,y)+countWays(x,y-1); }
dp:
int countWays(int x, int y) { int dp[12][12]; for(int i=0;i<x;i++){ for(int j=0;j<y;j++){ if(i==0&&j==0)dp[i][j]=1; else if(i==0&&j!=0)dp[i][j]=dp[i][j-1];//如果是上边界 else if(i!=0&&j==0)dp[i][j]=dp[i-1][j];//或者左边界,只能和上一次的位置往下/右走 else dp[i][j]=dp[i-1][j]+dp[i][j-1]; } } return dp[x-1][y-1]; }
机器人Ⅱ:
多了障碍,那么遇到障碍就要跳过:
int countWays(vector<vector<int>> map, int x, int y) { if(map[x][y]==1){ //遇到障碍就跳过 if(x==0&&y==0)return 1; else if(x==0&&y!=0)return countWays(map,x,y-1)%1000000007; else if(x!=0&&y==0)return countWays(map,x-1,y)%1000000007; else return (countWays(map,x-1,y)+countWays(map,x,y-1))%1000000007; }else return 0; }
dp:
int countWays(vector<vector<int>> map, int x, int y) { int dp[51][51]; for(int i=0;i<x;i++){ for(int j=0;j<y;j++){ if(map[i][j]==0){ dp[i][j]=0;continue; } if(i==0&&j!=0){ dp[0][j]=dp[0][j-1]; }else if(i!=0&&j==0){ dp[i][0]=dp[i-1][0]; }else if(i==0&&j==0){ dp[i][j]=1; }else{ dp[i][j]=(dp[i-1][j]+dp[i][j-1])%1000000007; } } }return dp[x-1][y-1]; }