Skip to content

Commit 984772f

Browse files
halfrosthalfrost
committed
Add solution 1293、2096
1 parent 200b308 commit 984772f

9 files changed

+719
-2
lines changed

‎leetcode/1293.Shortest-Path-in-a-Grid-with-Obstacles-Elimination/1293. Shortest Path in a Grid with Obstacles Elimination.go

Lines changed: 71 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,71 @@
1+
package leetcode
2+
3+
var dir = [][]int{
4+
{-1, 0},
5+
{0, 1},
6+
{1, 0},
7+
{0, -1},
8+
}
9+
10+
type pos struct {
11+
x, y int
12+
obstacle int
13+
step int
14+
}
15+
16+
func shortestPath(grid [][]int, k int) int {
17+
queue, m, n := []pos{}, len(grid), len(grid[0])
18+
visitor := make([][][]int, m)
19+
if len(grid) == 1 && len(grid[0]) == 1 {
20+
return 0
21+
}
22+
for i := 0; i < m; i++ {
23+
visitor[i] = make([][]int, n)
24+
for j := 0; j < n; j++ {
25+
visitor[i][j] = make([]int, k+1)
26+
}
27+
}
28+
visitor[0][0][0] = 1
29+
queue = append(queue, pos{x: 0, y: 0, obstacle: 0, step: 0})
30+
for len(queue) > 0 {
31+
size := len(queue)
32+
for size > 0 {
33+
size--
34+
node := queue[0]
35+
queue = queue[1:]
36+
for i := 0; i < len(dir); i++ {
37+
newX := node.x + dir[i][0]
38+
newY := node.y + dir[i][1]
39+
if newX == m-1 && newY == n-1 {
40+
if node.obstacle != 0 {
41+
if node.obstacle <= k {
42+
return node.step + 1
43+
} else {
44+
continue
45+
}
46+
}
47+
return node.step + 1
48+
}
49+
if isInBoard(grid, newX, newY) {
50+
if grid[newX][newY] == 1 {
51+
if node.obstacle+1 <= k && visitor[newX][newY][node.obstacle+1] != 1 {
52+
queue = append(queue, pos{x: newX, y: newY, obstacle: node.obstacle + 1, step: node.step + 1})
53+
visitor[newX][newY][node.obstacle+1] = 1
54+
}
55+
} else {
56+
if node.obstacle <= k && visitor[newX][newY][node.obstacle] != 1 {
57+
queue = append(queue, pos{x: newX, y: newY, obstacle: node.obstacle, step: node.step + 1})
58+
visitor[newX][newY][node.obstacle] = 1
59+
}
60+
}
61+
62+
}
63+
}
64+
}
65+
}
66+
return -1
67+
}
68+
69+
func isInBoard(board [][]int, x, y int) bool {
70+
return x >= 0 && x < len(board) && y >= 0 && y < len(board[0])
71+
}

‎leetcode/1293.Shortest-Path-in-a-Grid-with-Obstacles-Elimination/1293. Shortest Path in a Grid with Obstacles Elimination_test.go

Lines changed: 73 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,73 @@
1+
package leetcode
2+
3+
import (
4+
"fmt"
5+
"testing"
6+
)
7+
8+
type question1293 struct {
9+
para1293
10+
ans1293
11+
}
12+
13+
// para 是参数
14+
// one 代表第一个参数
15+
type para1293 struct {
16+
grid [][]int
17+
k int
18+
}
19+
20+
// ans 是答案
21+
// one 代表第一个答案
22+
type ans1293 struct {
23+
one int
24+
}
25+
26+
func Test_Problem1293(t *testing.T) {
27+
28+
qs := []question1293{
29+
30+
{
31+
para1293{[][]int{
32+
{0, 0, 0},
33+
}, 1},
34+
ans1293{2},
35+
},
36+
37+
{
38+
para1293{[][]int{
39+
{0, 1, 1}, {0, 1, 1}, {0, 0, 0}, {0, 1, 0}, {0, 1, 0},
40+
}, 2},
41+
ans1293{6},
42+
},
43+
44+
{
45+
para1293{[][]int{
46+
{0, 0, 0}, {1, 1, 0}, {0, 0, 0}, {0, 1, 1}, {0, 0, 0},
47+
}, 1},
48+
ans1293{6},
49+
},
50+
51+
{
52+
para1293{[][]int{
53+
{0, 1, 1}, {1, 1, 1}, {1, 0, 0},
54+
}, 1},
55+
ans1293{-1},
56+
},
57+
58+
{
59+
para1293{[][]int{
60+
{0},
61+
}, 1},
62+
ans1293{0},
63+
},
64+
}
65+
66+
fmt.Printf("------------------------Leetcode Problem 1293------------------------\n")
67+
68+
for _, q := range qs {
69+
_, p := q.ans1293, q.para1293
70+
fmt.Printf("【input】:%v 【output】:%v\n", p, shortestPath(p.grid, p.k))
71+
}
72+
fmt.Printf("\n\n\n")
73+
}

‎leetcode/1293.Shortest-Path-in-a-Grid-with-Obstacles-Elimination/README.md

Lines changed: 131 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,131 @@
1+
# [1293. Shortest Path in a Grid with Obstacles Elimination](https://leetcode.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/)
2+
3+
4+
5+
## 题目
6+
7+
You are given an m x n integer matrix grid where each cell is either 0 (empty) or 1 (obstacle). You can move up, down, left, or right from and to an empty cell in one step.
8+
9+
Return the minimum number of steps to walk from the upper left corner (0, 0) to the lower right corner (m - 1, n - 1) given that you can eliminate at most k obstacles. If it is not possible to find such walk return -1.
10+
11+
12+
13+
Example 1:
14+
15+
16+
![](https://assets.leetcode.com/uploads/2021/09/30/short1-grid.jpg)
17+
18+
19+
```
20+
Input: grid = [[0,0,0],[1,1,0],[0,0,0],[0,1,1],[0,0,0]], k = 1
21+
Output: 6
22+
Explanation:
23+
The shortest path without eliminating any obstacle is 10.
24+
The shortest path with one obstacle elimination at position (3,2) is 6. Such path is (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (3,2) -> (4,2).
25+
```
26+
27+
Example 2:
28+
29+
![](https://assets.leetcode.com/uploads/2021/09/30/short2-grid.jpg)
30+
31+
```
32+
Input: grid = [[0,1,1],[1,1,1],[1,0,0]], k = 1
33+
Output: -1
34+
Explanation: We need to eliminate at least two obstacles to find such a walk.
35+
```
36+
37+
Constraints:
38+
39+
- m == grid.length
40+
- n == grid[i].length
41+
- 1 <= m, n <= 40
42+
- 1 <= k <= m * n
43+
- grid[i][j] is either 0 or 1.
44+
- grid[0][0] == grid[m - 1][n - 1] == 0
45+
46+
47+
48+
## 题目大意
49+
50+
给你一个 m * n 的网格，其中每个单元格不是 0（空）就是 1（障碍物）。每一步，您都可以在空白单元格中上、下、左、右移动。
51+
52+
如果您 最多 可以消除 k 个障碍物，请找出从左上角 (0, 0) 到右下角 (m-1, n-1) 的最短路径，并返回通过该路径所需的步数。如果找不到这样的路径，则返回 -1 。
53+
54+
55+
## 解题思路
56+
57+
使用 BFS 遍历棋盘。这题比普通可达性问题多了一个障碍物的限制。这个也不难。每个点往周边四个方向扩展的时候，如果遇到障碍物，先算上这个障碍物，障碍物累积总个数小于 K 的时候，从障碍物的这个格子继续开始遍历。如果没有遇到障碍物，判断当前累积障碍物个数是否已经小于 K 个，如果小于 K 便继续遍历。如果大于 K，便终止此轮遍历。
58+
59+
## 代码
60+
61+
```go
62+
var dir = [][]int{
63+
{-1, 0},
64+
{0, 1},
65+
{1, 0},
66+
{0, -1},
67+
}
68+
69+
type pos struct {
70+
x, y int
71+
obstacle int
72+
step int
73+
}
74+
75+
func shortestPath(grid [][]int, k int) int {
76+
queue, m, n := []pos{}, len(grid), len(grid[0])
77+
visitor := make([][][]int, m)
78+
if len(grid) == 1 && len(grid[0]) == 1 {
79+
return 0
80+
}
81+
for i := 0; i < m; i++ {
82+
visitor[i] = make([][]int, n)
83+
for j := 0; j < n; j++ {
84+
visitor[i][j] = make([]int, k+1)
85+
}
86+
}
87+
visitor[0][0][0] = 1
88+
queue = append(queue, pos{x: 0, y: 0, obstacle: 0, step: 0})
89+
for len(queue) > 0 {
90+
size := len(queue)
91+
for size > 0 {
92+
size--
93+
node := queue[0]
94+
queue = queue[1:]
95+
for i := 0; i < len(dir); i++ {
96+
newX := node.x + dir[i][0]
97+
newY := node.y + dir[i][1]
98+
if newX == m-1 && newY == n-1 {
99+
if node.obstacle != 0 {
100+
if node.obstacle <= k {
101+
return node.step + 1
102+
} else {
103+
continue
104+
}
105+
}
106+
return node.step + 1
107+
}
108+
if isInBoard(grid, newX, newY) {
109+
if grid[newX][newY] == 1 {
110+
if node.obstacle+1 <= k && visitor[newX][newY][node.obstacle+1] != 1 {
111+
queue = append(queue, pos{x: newX, y: newY, obstacle: node.obstacle + 1, step: node.step + 1})
112+
visitor[newX][newY][node.obstacle+1] = 1
113+
}
114+
} else {
115+
if node.obstacle <= k && visitor[newX][newY][node.obstacle] != 1 {
116+
queue = append(queue, pos{x: newX, y: newY, obstacle: node.obstacle, step: node.step + 1})
117+
visitor[newX][newY][node.obstacle] = 1
118+
}
119+
}
120+
121+
}
122+
}
123+
}
124+
}
125+
return -1
126+
}
127+
128+
func isInBoard(board [][]int, x, y int) bool {
129+
return x >= 0 && x < len(board) && y >= 0 && y < len(board[0])
130+
}
131+
```

‎leetcode/2096.Step-By-Step-Directions-From-a-Binary-Tree-Node-to-Another/2096. Step-By-Step Directions From a Binary Tree Node to Another.go

Lines changed: 77 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,77 @@
1+
package leetcode
2+
3+
import (
4+
"github.com/halfrost/LeetCode-Go/structures"
5+
)
6+
7+
// TreeNode define
8+
type TreeNode = structures.TreeNode
9+
10+
/**
11+
* Definition for a binary tree node.
12+
* type TreeNode struct {
13+
* Val int
14+
* Left *TreeNode
15+
* Right *TreeNode
16+
* }
17+
*/
18+
19+
func getDirections(root *TreeNode, startValue int, destValue int) string {
20+
sPath, dPath := make([]byte, 0), make([]byte, 0)
21+
findPath(root, startValue, &sPath)
22+
findPath(root, destValue, &dPath)
23+
size, i := min(len(sPath), len(dPath)), 0
24+
for i < size {
25+
if sPath[len(sPath)-1-i] == dPath[len(dPath)-1-i] {
26+
i++
27+
} else {
28+
break
29+
}
30+
}
31+
sPath = sPath[:len(sPath)-i]
32+
replace(sPath)
33+
dPath = dPath[:len(dPath)-i]
34+
reverse(dPath)
35+
sPath = append(sPath, dPath...)
36+
return string(sPath)
37+
}
38+
39+
func findPath(root *TreeNode, value int, path *[]byte) bool {
40+
if root.Val == value {
41+
return true
42+
}
43+
44+
if root.Left != nil && findPath(root.Left, value, path) {
45+
*path = append(*path, 'L')
46+
return true
47+
}
48+
49+
if root.Right != nil && findPath(root.Right, value, path) {
50+
*path = append(*path, 'R')
51+
return true
52+
}
53+
54+
return false
55+
}
56+
57+
func reverse(path []byte) {
58+
left, right := 0, len(path)-1
59+
for left < right {
60+
path[left], path[right] = path[right], path[left]
61+
left++
62+
right--
63+
}
64+
}
65+
66+
func replace(path []byte) {
67+
for i := 0; i < len(path); i++ {
68+
path[i] = 'U'
69+
}
70+
}
71+
72+
func min(i, j int) int {
73+
if i < j {
74+
return i
75+
}
76+
return j
77+
}

0 commit comments

Comments
 (0)