Skip to content

Commit 0f1aee6

Browse files
yanglbmeyanglbme
committed
feat: add solutions to lc problem: No.1197
No.1197.Minimum Knight Moves
1 parent 01a242f commit 0f1aee6

File tree

2 files changed

+166
-0
lines changed

2 files changed

+166
-0
lines changed

‎solution/1100-1199/1197.Minimum Knight Moves/README.md

Lines changed: 83 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -74,6 +74,36 @@ class Solution:
7474
return -1
7575
```
7676

77+
双向 BFS；
78+
79+
```python
80+
class Solution:
81+
def minKnightMoves(self, x: int, y: int) -> int:
82+
def extend(m1, m2, q):
83+
for _ in range(len(q), 0, -1):
84+
i, j = q.popleft()
85+
step = m1[(i, j)]
86+
for a, b in [[-2, 1], [-1, 2], [1, 2], [2, 1], [2, -1], [1, -2], [-1, -2], [-2, -1]]:
87+
x, y = i + a, j + b
88+
if (x, y) in m1:
89+
continue
90+
if (x, y) in m2:
91+
return step + 1 + m2[(x, y)]
92+
q.append((x, y))
93+
m1[(x, y)] = step + 1
94+
return -1
95+
96+
if (x, y) == (0, 0):
97+
return 0
98+
q1, q2 = deque([(0, 0)]), deque([(x, y)])
99+
m1, m2 = {(0, 0): 0}, {(x, y): 0}
100+
while q1 and q2:
101+
t = extend(m1, m2, q1) if len(q1) <= len(q2) else extend(m2, m1, q2)
102+
if t != -1:
103+
return t
104+
return -1
105+
```
106+
77107
### **Java**
78108

79109
<!-- 这里可写当前语言的特殊实现逻辑 -->
@@ -111,6 +141,59 @@ class Solution {
111141
}
112142
```
113143

144+
双向 BFS：
145+
146+
```java
147+
class Solution {
148+
private int base = 310;
149+
private int n = 700;
150+
151+
public int minKnightMoves(int x, int y) {
152+
if (x == 0 && y == 0) {
153+
return 0;
154+
}
155+
x += base;
156+
y += base;
157+
Map<Integer, Integer> m1 = new HashMap<>();
158+
Map<Integer, Integer> m2 = new HashMap<>();
159+
m1.put(310 * n + 310, 0);
160+
m2.put(x * n + y, 0);
161+
Queue<int[]> q1 = new ArrayDeque<>();
162+
Queue<int[]> q2 = new ArrayDeque<>();
163+
q1.offer(new int[]{310, 310});
164+
q2.offer(new int[]{x, y});
165+
while (!q1.isEmpty() && !q2.isEmpty()) {
166+
int t = q1.size() <= q2.size() ? extend(m1, m2, q1) : extend(m2, m1, q2);
167+
if (t != -1) {
168+
return t;
169+
}
170+
}
171+
return -1;
172+
}
173+
174+
private int extend(Map<Integer, Integer> m1, Map<Integer, Integer> m2, Queue<int[]> q) {
175+
for (int k = q.size(); k > 0; --k) {
176+
int[] p = q.poll();
177+
int step = m1.get(p[0] * n + p[1]);
178+
int[][] dirs = {{-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}};
179+
for (int[] dir : dirs) {
180+
int x = p[0] + dir[0];
181+
int y = p[1] + dir[1];
182+
if (m1.containsKey(x * n + y)) {
183+
continue;
184+
}
185+
if (m2.containsKey(x * n + y)) {
186+
return step + 1 + m2.get(x * n + y);
187+
}
188+
m1.put(x * n + y, step + 1);
189+
q.offer(new int[]{x, y});
190+
}
191+
}
192+
return -1;
193+
}
194+
}
195+
```
196+
114197
### **C++**
115198

116199
```cpp

‎solution/1100-1199/1197.Minimum Knight Moves/README_EN.md

Lines changed: 83 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -64,6 +64,36 @@ class Solution:
6464
return -1
6565
```
6666

67+
Two-end BFS:
68+
69+
```python
70+
class Solution:
71+
def minKnightMoves(self, x: int, y: int) -> int:
72+
def extend(m1, m2, q):
73+
for _ in range(len(q), 0, -1):
74+
i, j = q.popleft()
75+
step = m1[(i, j)]
76+
for a, b in [[-2, 1], [-1, 2], [1, 2], [2, 1], [2, -1], [1, -2], [-1, -2], [-2, -1]]:
77+
x, y = i + a, j + b
78+
if (x, y) in m1:
79+
continue
80+
if (x, y) in m2:
81+
return step + 1 + m2[(x, y)]
82+
q.append((x, y))
83+
m1[(x, y)] = step + 1
84+
return -1
85+
86+
if (x, y) == (0, 0):
87+
return 0
88+
q1, q2 = deque([(0, 0)]), deque([(x, y)])
89+
m1, m2 = {(0, 0): 0}, {(x, y): 0}
90+
while q1 and q2:
91+
t = extend(m1, m2, q1) if len(q1) <= len(q2) else extend(m2, m1, q2)
92+
if t != -1:
93+
return t
94+
return -1
95+
```
96+
6797
### **Java**
6898

6999
```java
@@ -99,6 +129,59 @@ class Solution {
99129
}
100130
```
101131

132+
Two-end BFS:
133+
134+
```java
135+
class Solution {
136+
private int base = 310;
137+
private int n = 700;
138+
139+
public int minKnightMoves(int x, int y) {
140+
if (x == 0 && y == 0) {
141+
return 0;
142+
}
143+
x += base;
144+
y += base;
145+
Map<Integer, Integer> m1 = new HashMap<>();
146+
Map<Integer, Integer> m2 = new HashMap<>();
147+
m1.put(310 * n + 310, 0);
148+
m2.put(x * n + y, 0);
149+
Queue<int[]> q1 = new ArrayDeque<>();
150+
Queue<int[]> q2 = new ArrayDeque<>();
151+
q1.offer(new int[]{310, 310});
152+
q2.offer(new int[]{x, y});
153+
while (!q1.isEmpty() && !q2.isEmpty()) {
154+
int t = q1.size() <= q2.size() ? extend(m1, m2, q1) : extend(m2, m1, q2);
155+
if (t != -1) {
156+
return t;
157+
}
158+
}
159+
return -1;
160+
}
161+
162+
private int extend(Map<Integer, Integer> m1, Map<Integer, Integer> m2, Queue<int[]> q) {
163+
for (int k = q.size(); k > 0; --k) {
164+
int[] p = q.poll();
165+
int step = m1.get(p[0] * n + p[1]);
166+
int[][] dirs = {{-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}};
167+
for (int[] dir : dirs) {
168+
int x = p[0] + dir[0];
169+
int y = p[1] + dir[1];
170+
if (m1.containsKey(x * n + y)) {
171+
continue;
172+
}
173+
if (m2.containsKey(x * n + y)) {
174+
return step + 1 + m2.get(x * n + y);
175+
}
176+
m1.put(x * n + y, step + 1);
177+
q.offer(new int[]{x, y});
178+
}
179+
}
180+
return -1;
181+
}
182+
}
183+
```
184+
102185
### **C++**
103186

104187
```cpp

0 commit comments

Comments
 (0)