FilesExpand file tree

 master

/

UniquePathsII.cs

Copy path

BlameMore file actions

BlameMore file actions

Latest commit

 

History

History

History

executable file

·

61 lines (57 loc) · 3.37 KB

 master

/

UniquePathsII.cs

Top

File metadata and controls

• Code
• Blame

executable file

·

61 lines (57 loc) · 3.37 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

// Source : https://leetcode.com/problems/unique-paths-ii/

// Author : codeyu

// Date : Sunday, December 11, 2016 4:11:06 PM

/**********************************************************************************

*

* 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.

*

**********************************************************************************/

using System;

using System.Collections.Generic;

using Algorithms.Utils;

namespace Algorithms

{

public class Solution063

{

public static int UniquePathsWithObstacles(int[,] obstacleGrid)

{

if(obstacleGrid == null || obstacleGrid.GetLength(0)==0 || obstacleGrid.GetLength(1)==0)

return 0;

int[] res = new int[obstacleGrid.GetLength(1)];

res[0] = 1;

for(int i=0;i<obstacleGrid.GetLength(0);i++)

{

for(int j=0;j<obstacleGrid.GetLength(1);j++)

{

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

{

res[j]=0;

}

else

{

if(j>0)

res[j] += res[j-1];

}

}

}

return res[obstacleGrid.GetLength(1)-1];

}

}

}