Commitc35778c

committed

Lintcode/src/chapter4_DynamicProgrammingI/UniquePathsII.java

1 parent2f34d85 commitc35778cCopy full SHA for c35778c

File tree

+53

-0

lines changed

+53

-0

lines changed

Lines changed: 53 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,53 @@`
	`1`	`+packagechapter4_DynamicProgrammingI;`
	`2`	`+/**Follow up for "Unique Paths":`
	`3`	`+`
	`4`	`+Now consider if some obstacles are added to the grids. How many unique paths would there be?`
	`5`	`+`
	`6`	`+An obstacle and empty space is marked as 1 and 0 respectively in the grid.`
	`7`	`+`
	`8`	`+ Notice`
	`9`	`+`
	`10`	`+m and n will be at most 100.*/`
	`11`	`+publicclassUniquePathsII {`
	`12`	`+`
	`13`	`+/**`
	`14`	`+ * @param obstacleGrid: A list of lists of integers`
	`15`	`+ * @return: An integer`
	`16`	`+ */`
	`17`	`+publicintuniquePathsWithObstacles(int[][]obstacleGrid) {`
	`18`	`+// write your code here`
	`19`	`+if(obstacleGrid ==null \|\|obstacleGrid.length ==0)return0;`
	`20`	`+intm =obstacleGrid.length,n =obstacleGrid[0].length;`
	`21`	`+int[][]ways =newint[m][n];`
	`22`	`+`
	`23`	`+for(inti =0;i <m;i++){`
	`24`	`+if(obstacleGrid[i][0] ==0)ways[i][0] =1;`
	`25`	`+else {`
	`26`	`+while(i <m){`
	`27`	`+ways[i][0] =0;`
	`28`	`+i++;`
	`29`	`+ }`
	`30`	`+ }`
	`31`	`+ }`
	`32`	`+`
	`33`	`+for(intj =0;j <n;j++){`
	`34`	`+if(obstacleGrid[0][j] ==0)ways[0][j] =1;`
	`35`	`+else {`
	`36`	`+while(j <n){`
	`37`	`+ways[0][j] =0;`
	`38`	`+j++;`
	`39`	`+ }`
	`40`	`+ }`
	`41`	`+ }`
	`42`	`+`
	`43`	`+for(inti =1;i <m;i++){`
	`44`	`+for(intj =1;j <n;j++){`
	`45`	`+if(obstacleGrid[i][j] ==1)ways[i][j] =0;`
	`46`	`+elseways[i][j] =ways[i-1][j] +ways[i][j-1];`
	`47`	`+ }`
	`48`	`+ }`
	`49`	`+`
	`50`	`+returnways[m-1][n-1];`
	`51`	`+ }`
	`52`	`+`
	`53`	`+}`

Comments

(0)