題目描述

有一個XxY的網格，一個機器人只能走格點且只能向右或向下走，要從左上角走到右下角。請設計一個算法，計算機器人有多少種走法。注意這次的網格中有些障礙點是不能走的。

給定一個int[][]?map(C++ 中為vector >),表示網格圖，若map[i][j]為1則說明該點不是障礙點，否則則為障礙。另外給定int?x,int?y，表示網格的大小。請返回機器人從(0,0)走到(x - 1,y - 1)的走法數，為了防止溢出，請將結果Mod 1000000007。保證x和y均小于等于50

---

class Robot { public:int countWays(vector<vector<int> > map, int x, int y) {// write code here vector<vector<int>> dp(x,vector<int>(y,0));??????for(int i=0; i<x; i++){if(map[i][0] != 1){break;}dp[i][0] = 1;}for(int i=0; i<y; i++){if(map[0][i] != 1)break;dp[0][i] = 1;}for(int i=1;i<x;i++)for(int j=1;j<y;j++){if(map[i][j] == 1){dp[i][j] = (dp[i-1][j]+dp[i][j-1])%1000000007;}}return dp[x-1][y-1];?} };

?

總結

以上是生活随笔為你收集整理的【程序员面试金典】有一个XxY的网格，一个机器人只能走格点且只能向右或向下走，要从左上角走到右下角。请设计一个算法，计算机器人有多少种走法。注意这次的网格中有些障碍点是不能走的。的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。