Skip to content

Commit 24fe7cd

Browse files
yanglbmeyanglbme
committed
feat: add solutions to lc problem: No.0499
No.0499.The Maze III
1 parent d9e3485 commit 24fe7cd

File tree

6 files changed

+475
-2
lines changed

6 files changed

+475
-2
lines changed

‎solution/0400-0499/0499.The Maze III/README.md

Lines changed: 162 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -70,22 +70,183 @@
7070

7171
<!-- 这里可写通用的实现逻辑 -->
7272

73+
BFS。
74+
7375
<!-- tabs:start -->
7476

7577
### **Python3**
7678

7779
<!-- 这里可写当前语言的特殊实现逻辑 -->
7880

7981
```python
80-
82+
class Solution:
83+
def findShortestWay(self, maze: List[List[int]], ball: List[int], hole: List[int]) -> str:
84+
m, n = len(maze), len(maze[0])
85+
r, c = ball
86+
rh, ch = hole
87+
q = deque([(r, c)])
88+
dist = [[float('inf')] * n for _ in range(m)]
89+
dist[r][c] = 0
90+
path = [[None] * n for _ in range(m)]
91+
path[r][c] = ''
92+
while q:
93+
i, j = q.popleft()
94+
for a, b, d in [(-1, 0, 'u'), (1, 0, 'd'), (0, -1, 'l'), (0, 1, 'r')]:
95+
x, y, step = i, j, dist[i][j]
96+
while 0 <= x + a < m and 0 <= y + b < n and maze[x + a][y + b] == 0 and (x != rh or y != ch):
97+
x, y = x + a, y + b
98+
step += 1
99+
if dist[x][y] > step or (dist[x][y] == step and path[i][j] + d < path[x][y]):
100+
dist[x][y] = step
101+
path[x][y] = path[i][j] + d
102+
if x != rh or y != ch:
103+
q.append((x, y))
104+
return path[rh][ch] or 'impossible'
81105
```
82106

83107
### **Java**
84108

85109
<!-- 这里可写当前语言的特殊实现逻辑 -->
86110

87111
```java
112+
class Solution {
113+
public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
114+
int m = maze.length;
115+
int n = maze[0].length;
116+
int r = ball[0], c = ball[1];
117+
int rh = hole[0], ch = hole[1];
118+
Deque<int[]> q = new LinkedList<>();
119+
q.offer(new int[]{r, c});
120+
int[][] dist = new int[m][n];
121+
for (int i = 0; i < m; ++i) {
122+
Arrays.fill(dist[i], Integer.MAX_VALUE);
123+
}
124+
dist[r][c] = 0;
125+
String[][] path = new String[m][n];
126+
path[r][c] = "";
127+
int[][] dirs = {{-1, 0, 'u'}, {1, 0, 'd'}, {0, -1, 'l'}, {0, 1, 'r'}};
128+
while (!q.isEmpty()) {
129+
int[] p = q.poll();
130+
int i = p[0], j = p[1];
131+
for (int[] dir : dirs) {
132+
int a = dir[0], b = dir[1];
133+
String d = String.valueOf((char) (dir[2]));
134+
int x = i, y = j;
135+
int step = dist[i][j];
136+
while (x + a >= 0 && x + a < m && y + b >= 0 && y + b < n && maze[x + a][y + b] == 0 && (x != rh || y != ch)) {
137+
x += a;
138+
y += b;
139+
++step;
140+
}
141+
if (dist[x][y] > step || (dist[x][y] == step && (path[i][j] + d).compareTo(path[x][y]) < 0)) {
142+
dist[x][y] = step;
143+
path[x][y] = path[i][j] + d;
144+
if (x != rh || y != ch) {
145+
q.offer(new int[]{x, y});
146+
}
147+
}
148+
}
149+
}
150+
return path[rh][ch] == null ? "impossible" : path[rh][ch];
151+
}
152+
}
153+
```
154+
155+
### **C++**
156+
157+
```cpp
158+
class Solution {
159+
public:
160+
string findShortestWay(vector<vector<int>>& maze, vector<int>& ball, vector<int>& hole) {
161+
int m = maze.size();
162+
int n = maze[0].size();
163+
int r = ball[0], c = ball[1];
164+
int rh = hole[0], ch = hole[1];
165+
queue<pair<int, int>> q;
166+
q.push({r, c});
167+
vector<vector<int>> dist(m, vector<int>(n, INT_MAX));
168+
dist[r][c] = 0;
169+
vector<vector<string>> path(m, vector<string>(n, ""));
170+
vector<vector<int>> dirs = {{-1, 0, 'u'}, {1, 0, 'd'}, {0, -1, 'l'}, {0, 1, 'r'}};
171+
while (!q.empty())
172+
{
173+
auto p = q.front();
174+
q.pop();
175+
int i = p.first, j = p.second;
176+
for (auto& dir : dirs)
177+
{
178+
int a = dir[0], b = dir[1];
179+
char d = (char) dir[2];
180+
int x = i, y = j;
181+
int step = dist[i][j];
182+
while (x + a >= 0 && x + a < m && y + b >= 0 && y + b < n && maze[x + a][y + b] == 0 && (x != rh || y != ch))
183+
{
184+
x += a;
185+
y += b;
186+
++step;
187+
}
188+
if (dist[x][y] > step || (dist[x][y] == step && (path[i][j] + d < path[x][y])))
189+
{
190+
dist[x][y] = step;
191+
path[x][y] = path[i][j] + d;
192+
if (x != rh || y != ch) q.push({x, y});
193+
}
194+
}
195+
}
196+
return path[rh][ch] == "" ? "impossible" : path[rh][ch];
197+
}
198+
};
199+
```
88200
201+
### **Go**
202+
203+
```go
204+
import "math"
205+
206+
func findShortestWay(maze [][]int, ball []int, hole []int) string {
207+
m, n := len(maze), len(maze[0])
208+
r, c := ball[0], ball[1]
209+
rh, ch := hole[0], hole[1]
210+
q := [][]int{[]int{r, c}}
211+
dist := make([][]int, m)
212+
path := make([][]string, m)
213+
for i := range dist {
214+
dist[i] = make([]int, n)
215+
path[i] = make([]string, n)
216+
for j := range dist[i] {
217+
dist[i][j] = math.MaxInt32
218+
path[i][j] = ""
219+
}
220+
}
221+
dist[r][c] = 0
222+
dirs := map[string][]int{"u": {-1, 0}, "d": {1, 0}, "l": {0, -1}, "r": {0, 1}}
223+
for len(q) > 0 {
224+
p := q[0]
225+
q = q[1:]
226+
i, j := p[0], p[1]
227+
for d, dir := range dirs {
228+
a, b := dir[0], dir[1]
229+
x, y := i, j
230+
step := dist[i][j]
231+
for x+a >= 0 && x+a < m && y+b >= 0 && y+b < n && maze[x+a][y+b] == 0 && (x != rh || y != ch) {
232+
x += a
233+
y += b
234+
step++
235+
}
236+
if dist[x][y] > step || (dist[x][y] == step && (path[i][j]+d) < path[x][y]) {
237+
dist[x][y] = step
238+
path[x][y] = path[i][j] + d
239+
if x != rh || y != ch {
240+
q = append(q, []int{x, y})
241+
}
242+
}
243+
}
244+
}
245+
if path[rh][ch] == "" {
246+
return "impossible"
247+
}
248+
return path[rh][ch]
249+
}
89250
```
90251

91252
### **...**

‎solution/0400-0499/0499.The Maze III/README_EN.md

Lines changed: 162 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -59,18 +59,179 @@ Both ways have shortest distance 6, but the first way is lexicographically small
5959

6060
## Solutions
6161

62+
BFS.
63+
6264
<!-- tabs:start -->
6365

6466
### **Python3**
6567

6668
```python
67-
69+
class Solution:
70+
def findShortestWay(self, maze: List[List[int]], ball: List[int], hole: List[int]) -> str:
71+
m, n = len(maze), len(maze[0])
72+
r, c = ball
73+
rh, ch = hole
74+
q = deque([(r, c)])
75+
dist = [[float('inf')] * n for _ in range(m)]
76+
dist[r][c] = 0
77+
path = [[None] * n for _ in range(m)]
78+
path[r][c] = ''
79+
while q:
80+
i, j = q.popleft()
81+
for a, b, d in [(-1, 0, 'u'), (1, 0, 'd'), (0, -1, 'l'), (0, 1, 'r')]:
82+
x, y, step = i, j, dist[i][j]
83+
while 0 <= x + a < m and 0 <= y + b < n and maze[x + a][y + b] == 0 and (x != rh or y != ch):
84+
x, y = x + a, y + b
85+
step += 1
86+
if dist[x][y] > step or (dist[x][y] == step and path[i][j] + d < path[x][y]):
87+
dist[x][y] = step
88+
path[x][y] = path[i][j] + d
89+
if x != rh or y != ch:
90+
q.append((x, y))
91+
return path[rh][ch] or 'impossible'
6892
```
6993

7094
### **Java**
7195

7296
```java
97+
class Solution {
98+
public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
99+
int m = maze.length;
100+
int n = maze[0].length;
101+
int r = ball[0], c = ball[1];
102+
int rh = hole[0], ch = hole[1];
103+
Deque<int[]> q = new LinkedList<>();
104+
q.offer(new int[]{r, c});
105+
int[][] dist = new int[m][n];
106+
for (int i = 0; i < m; ++i) {
107+
Arrays.fill(dist[i], Integer.MAX_VALUE);
108+
}
109+
dist[r][c] = 0;
110+
String[][] path = new String[m][n];
111+
path[r][c] = "";
112+
int[][] dirs = {{-1, 0, 'u'}, {1, 0, 'd'}, {0, -1, 'l'}, {0, 1, 'r'}};
113+
while (!q.isEmpty()) {
114+
int[] p = q.poll();
115+
int i = p[0], j = p[1];
116+
for (int[] dir : dirs) {
117+
int a = dir[0], b = dir[1];
118+
String d = String.valueOf((char) (dir[2]));
119+
int x = i, y = j;
120+
int step = dist[i][j];
121+
while (x + a >= 0 && x + a < m && y + b >= 0 && y + b < n && maze[x + a][y + b] == 0 && (x != rh || y != ch)) {
122+
x += a;
123+
y += b;
124+
++step;
125+
}
126+
if (dist[x][y] > step || (dist[x][y] == step && (path[i][j] + d).compareTo(path[x][y]) < 0)) {
127+
dist[x][y] = step;
128+
path[x][y] = path[i][j] + d;
129+
if (x != rh || y != ch) {
130+
q.offer(new int[]{x, y});
131+
}
132+
}
133+
}
134+
}
135+
return path[rh][ch] == null ? "impossible" : path[rh][ch];
136+
}
137+
}
138+
```
139+
140+
### **C++**
141+
142+
```cpp
143+
class Solution {
144+
public:
145+
string findShortestWay(vector<vector<int>>& maze, vector<int>& ball, vector<int>& hole) {
146+
int m = maze.size();
147+
int n = maze[0].size();
148+
int r = ball[0], c = ball[1];
149+
int rh = hole[0], ch = hole[1];
150+
queue<pair<int, int>> q;
151+
q.push({r, c});
152+
vector<vector<int>> dist(m, vector<int>(n, INT_MAX));
153+
dist[r][c] = 0;
154+
vector<vector<string>> path(m, vector<string>(n, ""));
155+
vector<vector<int>> dirs = {{-1, 0, 'u'}, {1, 0, 'd'}, {0, -1, 'l'}, {0, 1, 'r'}};
156+
while (!q.empty())
157+
{
158+
auto p = q.front();
159+
q.pop();
160+
int i = p.first, j = p.second;
161+
for (auto& dir : dirs)
162+
{
163+
int a = dir[0], b = dir[1];
164+
char d = (char) dir[2];
165+
int x = i, y = j;
166+
int step = dist[i][j];
167+
while (x + a >= 0 && x + a < m && y + b >= 0 && y + b < n && maze[x + a][y + b] == 0 && (x != rh || y != ch))
168+
{
169+
x += a;
170+
y += b;
171+
++step;
172+
}
173+
if (dist[x][y] > step || (dist[x][y] == step && (path[i][j] + d < path[x][y])))
174+
{
175+
dist[x][y] = step;
176+
path[x][y] = path[i][j] + d;
177+
if (x != rh || y != ch) q.push({x, y});
178+
}
179+
}
180+
}
181+
return path[rh][ch] == "" ? "impossible" : path[rh][ch];
182+
}
183+
};
184+
```
73185
186+
### **Go**
187+
188+
```go
189+
import "math"
190+
191+
func findShortestWay(maze [][]int, ball []int, hole []int) string {
192+
m, n := len(maze), len(maze[0])
193+
r, c := ball[0], ball[1]
194+
rh, ch := hole[0], hole[1]
195+
q := [][]int{[]int{r, c}}
196+
dist := make([][]int, m)
197+
path := make([][]string, m)
198+
for i := range dist {
199+
dist[i] = make([]int, n)
200+
path[i] = make([]string, n)
201+
for j := range dist[i] {
202+
dist[i][j] = math.MaxInt32
203+
path[i][j] = ""
204+
}
205+
}
206+
dist[r][c] = 0
207+
dirs := map[string][]int{"u": {-1, 0}, "d": {1, 0}, "l": {0, -1}, "r": {0, 1}}
208+
for len(q) > 0 {
209+
p := q[0]
210+
q = q[1:]
211+
i, j := p[0], p[1]
212+
for d, dir := range dirs {
213+
a, b := dir[0], dir[1]
214+
x, y := i, j
215+
step := dist[i][j]
216+
for x+a >= 0 && x+a < m && y+b >= 0 && y+b < n && maze[x+a][y+b] == 0 && (x != rh || y != ch) {
217+
x += a
218+
y += b
219+
step++
220+
}
221+
if dist[x][y] > step || (dist[x][y] == step && (path[i][j]+d) < path[x][y]) {
222+
dist[x][y] = step
223+
path[x][y] = path[i][j] + d
224+
if x != rh || y != ch {
225+
q = append(q, []int{x, y})
226+
}
227+
}
228+
}
229+
}
230+
if path[rh][ch] == "" {
231+
return "impossible"
232+
}
233+
return path[rh][ch]
234+
}
74235
```
75236

76237
### **...**

0 commit comments

Comments
 (0)