Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitbc98d9f

Browse files
add md articles (#5137)
* add the-maze-iii.md article* add minimum-knight-moves.md article
1 parentf7cc5e1 commitbc98d9f

File tree

2 files changed

+659
-0
lines changed

2 files changed

+659
-0
lines changed

‎articles/minimum-knight-moves.md‎

Lines changed: 323 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,323 @@
1+
##1. BFS (Breadth-First Search)
2+
3+
::tabs-start
4+
5+
```python
6+
classSolution:
7+
defminKnightMoves(self,x:int,y:int) ->int:
8+
# the offsets in the eight directions
9+
offsets= [(1,2), (2,1), (2,-1), (1,-2),
10+
(-1,-2), (-2,-1), (-2,1), (-1,2)]
11+
12+
defbfs(x,y):
13+
visited=set()
14+
queue= deque([(0,0)])
15+
steps=0
16+
17+
while queue:
18+
curr_level_cnt=len(queue)
19+
# iterate through the current level
20+
for iinrange(curr_level_cnt):
21+
curr_x, curr_y= queue.popleft()
22+
if (curr_x, curr_y)== (x, y):
23+
return steps
24+
25+
for offset_x, offset_yin offsets:
26+
next_x, next_y= curr_x+ offset_x, curr_y+ offset_y
27+
if (next_x, next_y)notin visited:
28+
visited.add((next_x, next_y))
29+
queue.append((next_x, next_y))
30+
31+
# move on to the next level
32+
steps+=1
33+
34+
return bfs(x, y)
35+
```
36+
37+
```java
38+
classSolution {
39+
publicintminKnightMoves(intx,inty) {
40+
// the offsets in the eight directions
41+
int[][] offsets= {{1,2}, {2,1}, {2,-1}, {1,-2},
42+
{-1,-2}, {-2,-1}, {-2,1}, {-1,2}};
43+
44+
// - Rather than using the inefficient HashSet, we use the bitmap
45+
// otherwise we would run out of time for the test cases.
46+
// - We create a bitmap that is sufficient to cover all the possible
47+
// inputs, according to the description of the problem.
48+
boolean[][] visited=newboolean[607][607];
49+
50+
Deque<int[]> queue=newLinkedList<>();
51+
queue.addLast(newint[]{0,0});
52+
int steps=0;
53+
54+
while (queue.size()>0) {
55+
int currLevelSize= queue.size();
56+
// iterate through the current level
57+
for (int i=0; i< currLevelSize; i++) {
58+
int[] curr= queue.removeFirst();
59+
if (curr[0]== x&& curr[1]== y) {
60+
return steps;
61+
}
62+
63+
for (int[] offset: offsets) {
64+
int[] next=newint[]{curr[0]+ offset[0], curr[1]+ offset[1]};
65+
// align the coordinate to the bitmap
66+
if (!visited[next[0]+302][next[1]+302]) {
67+
visited[next[0]+302][next[1]+302]=true;
68+
queue.addLast(next);
69+
}
70+
}
71+
}
72+
steps++;
73+
}
74+
// move on to the next level
75+
return steps;
76+
}
77+
}
78+
```
79+
80+
::tabs-end
81+
82+
###Time & Space Complexity
83+
84+
- Time complexity: $O\left(\left(\max(|x|, |y|)\right)^2\right)$
85+
- Space complexity: $O\left(\left(\max(|x|, |y|)\right)^2\right)$
86+
87+
> Where $(x,y)$ is the coordinate of the target.
88+
89+
---
90+
91+
##2. Bidirectional BFS
92+
93+
::tabs-start
94+
95+
```python
96+
classSolution:
97+
defminKnightMoves(self,x:int,y:int) ->int:
98+
# the offsets in the eight directions
99+
offsets= [(1,2), (2,1), (2,-1), (1,-2),
100+
(-1,-2), (-2,-1), (-2,1), (-1,2)]
101+
102+
# data structures needed to move from the origin point
103+
origin_queue= deque([(0,0,0)])
104+
origin_distance= {(0,0):0}
105+
106+
# data structures needed to move from the target point
107+
target_queue= deque([(x, y,0)])
108+
target_distance= {(x, y):0}
109+
110+
whileTrue:
111+
# check if we reach the circle of target
112+
origin_x, origin_y, origin_steps= origin_queue.popleft()
113+
if (origin_x, origin_y)in target_distance:
114+
return origin_steps+ target_distance[(origin_x, origin_y)]
115+
116+
# check if we reach the circle of origin
117+
target_x, target_y, target_steps= target_queue.popleft()
118+
if (target_x, target_y)in origin_distance:
119+
return target_steps+ origin_distance[(target_x, target_y)]
120+
121+
for offset_x, offset_yin offsets:
122+
# expand the circle of origin
123+
next_origin_x, next_origin_y= origin_x+ offset_x, origin_y+ offset_y
124+
if (next_origin_x, next_origin_y)notin origin_distance:
125+
origin_queue.append((next_origin_x, next_origin_y, origin_steps+1))
126+
origin_distance[(next_origin_x, next_origin_y)]= origin_steps+1
127+
128+
# expand the circle of target
129+
next_target_x, next_target_y= target_x+ offset_x, target_y+ offset_y
130+
if (next_target_x, next_target_y)notin target_distance:
131+
target_queue.append((next_target_x, next_target_y, target_steps+1))
132+
target_distance[(next_target_x, next_target_y)]= target_steps+1
133+
```
134+
135+
```java
136+
classSolution {
137+
publicintminKnightMoves(intx,inty) {
138+
// the offsets in the eight directions
139+
int[][] offsets= {{1,2}, {2,1}, {2,-1}, {1,-2},
140+
{-1,-2}, {-2,-1}, {-2,1}, {-1,2}};
141+
142+
// data structures needed to move from the origin point
143+
Deque<int[]> originQueue=newLinkedList<>();
144+
originQueue.addLast(newint[]{0,0,0});
145+
Map<String,Integer> originDistance=newHashMap<>();
146+
originDistance.put("0,0",0);
147+
148+
// data structures needed to move from the target point
149+
Deque<int[]> targetQueue=newLinkedList<>();
150+
targetQueue.addLast(newint[]{x, y,0});
151+
Map<String,Integer> targetDistance=newHashMap<>();
152+
targetDistance.put(x+","+ y,0);
153+
154+
while (true) {
155+
// check if we reach the circle of target
156+
int[] origin= originQueue.removeFirst();
157+
String originXY= origin[0]+","+ origin[1];
158+
if (targetDistance.containsKey(originXY)) {
159+
return origin[2]+ targetDistance.get(originXY);
160+
}
161+
162+
// check if we reach the circle of origin
163+
int[] target= targetQueue.removeFirst();
164+
String targetXY= target[0]+","+ target[1];
165+
if (originDistance.containsKey(targetXY)) {
166+
return target[2]+ originDistance.get(targetXY);
167+
}
168+
169+
for (int[] offset: offsets) {
170+
// expand the circle of origin
171+
int[] nextOrigin=newint[]{origin[0]+ offset[0], origin[1]+ offset[1]};
172+
String nextOriginXY= nextOrigin[0]+","+ nextOrigin[1];
173+
if (!originDistance.containsKey(nextOriginXY)) {
174+
originQueue.addLast(newint[]{nextOrigin[0], nextOrigin[1], origin[2]+1});
175+
originDistance.put(nextOriginXY, origin[2]+1);
176+
}
177+
178+
// expand the circle of target
179+
int[] nextTarget=newint[]{target[0]+ offset[0], target[1]+ offset[1]};
180+
String nextTargetXY= nextTarget[0]+","+ nextTarget[1];
181+
if (!targetDistance.containsKey(nextTargetXY)) {
182+
targetQueue.addLast(newint[]{nextTarget[0], nextTarget[1], target[2]+1});
183+
targetDistance.put(nextTargetXY, target[2]+1);
184+
}
185+
}
186+
}
187+
}
188+
}
189+
```
190+
191+
::tabs-end
192+
193+
###Time & Space Complexity
194+
195+
- Time complexity: $O\left(\left(\max(|x|, |y|)\right)^2\right)$
196+
- Space complexity: $O\left(\left(\max(|x|, |y|)\right)^2\right)$
197+
198+
> Where $(x,y)$ is the coordinate of the target.
199+
200+
---
201+
202+
##3. DFS (Depth-First Search) with Memoization
203+
204+
::tabs-start
205+
206+
```python
207+
classSolution:
208+
defminKnightMoves(self,x:int,y:int) ->int:
209+
210+
@lru_cache(maxsize=None)
211+
defdfs(x,y):
212+
if x+ y==0:
213+
# base case: (0, 0)
214+
return0
215+
elif x+ y==2:
216+
# base case: (1, 1), (0, 2), (2, 0)
217+
return2
218+
else:
219+
returnmin(dfs(abs(x-1),abs(y-2)), dfs(abs(x-2),abs(y-1)))+1
220+
221+
return dfs(abs(x),abs(y))
222+
```
223+
224+
```java
225+
classSolution {
226+
227+
privateMap<String,Integer> memo=newHashMap<>();
228+
229+
privateintdfs(intx,inty) {
230+
String key= x+","+ y;
231+
if (memo.containsKey(key)) {
232+
return memo.get(key);
233+
}
234+
235+
if (x+ y==0) {
236+
return0;
237+
}elseif (x+ y==2) {
238+
return2;
239+
}else {
240+
Integer ret=Math.min(dfs(Math.abs(x-1),Math.abs(y-2)),
241+
dfs(Math.abs(x-2),Math.abs(y-1)))+1;
242+
memo.put(key, ret);
243+
return ret;
244+
}
245+
}
246+
247+
publicintminKnightMoves(intx,inty) {
248+
return dfs(Math.abs(x),Math.abs(y));
249+
}
250+
}
251+
```
252+
253+
```cpp
254+
classSolution {
255+
private:
256+
unordered_map<string, int> memo;
257+
258+
int dfs(int x, int y) {
259+
string key = to_string(x) + "," + to_string(y);
260+
if (memo.find(key) != memo.end()) {
261+
return memo[key];
262+
}
263+
264+
if (x + y == 0) {
265+
return 0;
266+
} else if (x + y == 2) {
267+
return 2;
268+
} else {
269+
int ret = min(dfs(abs(x - 1), abs(y - 2)),
270+
dfs(abs(x - 2), abs(y - 1))) + 1;
271+
memo[key] = ret;
272+
return ret;
273+
}
274+
}
275+
276+
public:
277+
int minKnightMoves(int x, int y) {
278+
return dfs(abs(x), abs(y));
279+
}
280+
};
281+
```
282+
283+
```javascript
284+
class Solution {
285+
/**
286+
* @param {number} x
287+
* @param {number} y
288+
* @return {number}
289+
*/
290+
minKnightMoves(x, y) {
291+
const memo = new Map();
292+
293+
const dfs = (x, y) => {
294+
const key = `${x},${y}`;
295+
if (memo.has(key)) {
296+
return memo.get(key);
297+
}
298+
299+
if (x + y === 0) {
300+
return 0;
301+
} else if (x + y === 2) {
302+
return 2;
303+
} else {
304+
const ret = Math.min(dfs(Math.abs(x - 1), Math.abs(y - 2)),
305+
dfs(Math.abs(x - 2), Math.abs(y - 1))) + 1;
306+
memo.set(key, ret);
307+
return ret;
308+
}
309+
};
310+
311+
return dfs(Math.abs(x), Math.abs(y));
312+
}
313+
}
314+
```
315+
316+
::tabs-end
317+
318+
###Time & Space Complexity
319+
320+
- Time complexity: $O(|x \cdot y|)$
321+
- Space complexity: $O(|x \cdot y|)$
322+
323+
> Where $(x,y)$ is the coordinate of the target.

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp