## UniquePathsII.java ( File view )

• By issaczr 2014-10-24
• View(s)：52
• Point(s)： 1
```			// Author:   Li Long, 1988lilong@163.com
// Date:     Apr 17, 2014
// Source:   http://oj.leetcode.com/problems/unique-paths-ii/
// Analysis: http://blog.csdn.net/lilong_dream/article/details/19931301

// Follow up for "Unique Paths":
// Now consider if some obstacles are added to the grids.
// How many unique paths would there be?
// An obstacle and empty space is marked as 1 and 0 respectively in the grid.
// For example,
// There is one obstacle in the middle of a 3x3 grid as illustrated below.
//  [
//   [0,0,0],
//   [0,1,0],
//   [0,0,0]
// ]
// The total number of unique paths is 2.
// Note: m and n will be at most 100.

public class UniquePathsII {

public int uniquePathsWithObstacles(int[][] obstacleGrid) {

int m = obstacleGrid.length;
// if (m == 0) {

// 	   return 0;
//
}

int n = obstacleGrid[0].length;

if (obstacleGrid[0][0] == 1) {

return 0;

} else if (m == 1 && n == 1) {

return 1;

}

int[][] paths = new int[m][n];

for (int i = 0; i < m; ++i) {

if (obstacleGrid[i][0] == 1) {

while (i < m) {

paths[i][0] = 0;
++i;

}
break;

} else {

paths[i][0] = 1;

}

}

for (int j = 1; j < n; ++j) {

if (obstacleGrid[0][j] == 1) {

while (j < n) {

paths[0][j] = 0;
++j;

}
break;

} else {

paths[0][j] = 1;

}

}

for (int i = 1; i < m; ++i)
for (int j = 1; j < n; ++j) {

if (obstacleGrid[i][j] == 1) {

paths[i][j] = 0;

} else {

paths[i][j] = paths[i][j - 1] + paths[i - 1][j];

}

}

return paths[m - 1][n - 1];

}

public static void main(String[] args) {

int[][] obstacle = new int[][] {
{
0, 0, 0
}, {
0, 1, 0
}, {
0, 0, 0
}
};
UniquePathsII slt = new UniquePathsII();
int result = slt.uniquePathsWithObstacles(obstacle);
System.out.println(result);

}

}			```
...
Expand＞ ＜Close

Point(s): 1

0 lines left, continue to read

## File list

Tips: You can preview the content of files by clicking file names^_^
Name Size Date
01.97 kB
01.97 kB
BinaryTreePreorderTraversal.java1.91 kB2014-05-09 03:48
ClimbingStairs.java811.00 B2014-05-09 03:48
EvaluateReversePolishNotation.java1.51 kB2014-05-09 03:48
GenerateParentheses.java1.15 kB2014-05-09 03:48
ImplementStrStr.java1.00 kB2014-05-09 03:48
InsertionSortList.java1.64 kB2014-05-09 03:48
IntegerToRoman.java923.00 B2014-05-09 03:48
LengthOfLastWord.java1.11 kB2014-05-09 03:48
LongestCommonPrefix.java916.00 B2014-05-09 03:48
LongestSubstring.java1.79 kB2014-05-09 03:48
MaximumSubarray.java1.10 kB2014-05-09 03:48
MedianOfTwoSortedArrays.java1.68 kB2014-05-09 03:48
MergeSortedArray.java1.12 kB2014-05-09 03:48
MergeTwoSortedLists.java1.84 kB2014-05-09 03:48
MinimumPathSum.java1.19 kB2014-05-09 03:48
PathSum.java1.67 kB2014-05-09 03:48
PlusOne.java1.06 kB2014-05-09 03:48
Powxn.java712.00 B2014-05-09 03:48
RemoveDuplicatesFromSortedList.java1.48 kB2014-05-09 03:48
RemoveDuplicatesfromSortedArray.java1.30 kB2014-05-09 03:48
RemoveElement.java885.00 B2014-05-09 03:48
RemoveNthNodeFromEnd.java1.70 kB2014-05-09 03:48
ReverseInteger.java936.00 B2014-05-09 03:48
RotateList.java1.53 kB2014-05-09 03:48
SameTree.java1.15 kB2014-05-09 03:48
SearchForARange.java1.37 kB2014-05-09 03:48
SearchInRotatedSortedArray.java1.27 kB2014-05-09 03:48
SearchInsertPosition.java1.09 kB2014-05-09 03:48
SetMatrixZeroes.java1.95 kB2014-05-09 03:48
SingleNumber.java935.00 B2014-05-09 03:48
SortList.java1.75 kB2014-05-09 03:48
Sqrt.java907.00 B2014-05-09 03:48
StringToInteger_atoi.java1.46 kB2014-05-09 03:48
Sum3.java1.76 kB2014-05-09 03:48
TwoSum.java2.33 kB2014-05-09 03:48
UniqueBinarySearchTrees.java1.01 kB2014-05-09 03:48
UniquePaths.java976.00 B2014-05-09 03:48
UniquePathsII.java1.84 kB2014-05-09 03:48
ValidParentheses.java1.23 kB2014-05-09 03:48
ValidateBinarySearchTree.java1.44 kB2014-05-09 03:48
...
• Sent successfully!
• LeetCode-Java-master.zip
• 1 point

### UniquePathsII.java (35.66 kB)

Need 1 point

Get point immediately by PayPal

More(Debit card / Credit card / PayPal Credit / Online Banking)

Submit your source codes. Get more point

Don't have an account？ Register now
Need any help?
Mail to: support@codeforge.com

### 切换到中文版？

CodeForge Chinese Version
CodeForge English Version

### ^_^"Oops ...

Sorry!This guy is mysterious, its blog hasn't been opened, try another, please!

### Warm tip!

Favorite by Ctrl+D