未分類

Unique Paths II

Array, DynamicProgramming, Go, LeetCode

Unique Paths II

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.

1
2
3
4
5
[
  [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.

提示 解題應用
Array Array/Slice
DynamicProgramming 規律觀查

Default:

1
2
3
func uniquePathsWithObstacles(obstacleGrid [][]int) int {
}

解答思路:

建議可以先參考先前Unique Paths的解法，解說較為詳細，基本上概念完全一樣，只是將先前題的程式碼做修改而已，如果能找出mxn走到最右下角的所有組合數，當然要再篩選掉不能走的路線就不會太困難。

一開始也是初始化一相同大小的二元陣列用來紀錄mxn走到每格的所有組合數，接著從起點走到最左側或最下側雖然只有一種可能，但如果中間出現障礙物的話就沒辦法走到後頭初始值就要為0(障礙物到最左側或最下側之間的所有格子走法皆為0)，而再從起點鄰近的格子慢慢推算該格的走法是由到左側格子的走法再加上上側格子的走法時，如果該格本身的位置就是障礙物的位置，就直接將0取代原本要相加的總走法，最後不斷推倒到最右下角的格子就是我們要的結果

程式碼解說:

一樣在一開始就需要初始化二元陣列來紀錄mxn走到每格的所有組合數，所以就先取得包含障礙物的二元陣列的大小有幾橫排m與幾直列n，使我們能初始化一模一樣大小的二元陣列

1
2
3
4
5
6
7
var paths [][]int
var obstacle bool
m := len(obstacleGrid)
n := len(obstacleGrid[0])
for k := 1; k <= m; k++ {
	paths = append(paths, make([]int, n))
}

接著如果第一橫排與第一直列中間沒有出現障礙物的話就設初始值為1，因為一開始走到最左側或最下側都只有一種可能，但如果中間出現障礙物的話，障礙物到最左側或最下側之間的所有格子走法皆為0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
for i := 0; i < m; i++ {
	if obstacleGrid[i][0] == 1 {
		obstacle = true
	}
	if !obstacle {
		paths[i][0] = 1
	}
}
obstacle = false
for j := 0; j < n; j++ {
	if obstacleGrid[0][j] == 1 {
		obstacle = true
	}
	if !obstacle {
		paths[0][j] = 1
	}
}

最後則是根據先前所發現的規律，每格的走法都是由到左側格子的走法再加上上側格子的走法，將剩下的格子依序由左上到右下推倒，如果該格本身的位置就是障礙物的位置，就直接將0取代原本要相加的總走法，待最右下角格子的走法數算出來後就是我們要的結果

1
2
3
4
5
6
7
8
9
10
for i := 1; i < m; i++ {
	for j := 1; j < n; j++ {
		if obstacleGrid[i][j] == 1 {
			paths[i][j] = 0
		} else {
			paths[i][j] = paths[i-1][j] + paths[i][j-1]
		}
	}
}
return paths[m-1][n-1]

完整程式碼:

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
func uniquePathsWithObstacles(obstacleGrid [][]int) int {
	var paths [][]int
	var obstacle bool
	m := len(obstacleGrid)
	n := len(obstacleGrid[0])
	for k := 1; k <= m; k++ {
		paths = append(paths, make([]int, n))
	}
	for i := 0; i < m; i++ {
		if obstacleGrid[i][0] == 1 {
			obstacle = true
		}
		if !obstacle {
			paths[i][0] = 1
		}
	}
	obstacle = false
	for j := 0; j < n; j++ {
		if obstacleGrid[0][j] == 1 {
			obstacle = true
		}
		if !obstacle {
			paths[0][j] = 1
		}
	}
	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
			if obstacleGrid[i][j] == 1 {
				paths[i][j] = 0
			} else {
				paths[i][j] = paths[i-1][j] + paths[i][j-1]
			}
		}
	}
	return paths[m-1][n-1]
}

總結:

建議可以先參考先前Unique Paths的解法，解說較為詳細，基本上概念完全一樣，其做法就是先從簡單的部分開始以每格或點判斷走到該格有幾種可能，如果是從起點走到最左側或最下側時中間出現障礙物的話，障礙物到最左側或最下側之間的所有格子走法皆為0，接著從起點鄰近的格子慢慢推算該格的走法是由到左側格子的走法再加上上側格子的走法時，如果該格本身的位置就是障礙物的位置，就直接將0取代原本要相加的總走法，最後不斷推倒到最右下角的格子就是我們要的結果。

分享到