Skip to content

Commit 01a242f

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

File tree

10 files changed

+350
-6
lines changed

10 files changed

+350
-6
lines changed

‎solution/1000-1099/1091.Shortest Path in Binary Matrix/README.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -55,7 +55,7 @@
5555

5656
<!-- 这里可写通用的实现逻辑 -->
5757

58-
BFS 最短路问题。
58+
BFS 最短路模型。
5959

6060
<!-- tabs:start -->
6161

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

Lines changed: 119 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -46,22 +46,140 @@
4646

4747
<!-- 这里可写通用的实现逻辑 -->
4848

49+
BFS 最短路模型。
50+
4951
<!-- tabs:start -->
5052

5153
### **Python3**
5254

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

5557
```python
56-
58+
class Solution:
59+
def minKnightMoves(self, x: int, y: int) -> int:
60+
q = deque([(0, 0)])
61+
ans = 0
62+
vis = set([(0, 0)])
63+
while q:
64+
for _ in range(len(q), 0, -1):
65+
i, j = q.popleft()
66+
if (i, j) == (x, y):
67+
return ans
68+
for a, b in [[-2, 1], [-1, 2], [1, 2], [2, 1], [2, -1], [1, -2], [-1, -2], [-2, -1]]:
69+
c, d = i + a, j + b
70+
if (c, d) not in vis:
71+
vis.add((c, d))
72+
q.append((c, d))
73+
ans += 1
74+
return -1
5775
```
5876

5977
### **Java**
6078

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

6381
```java
82+
class Solution {
83+
public int minKnightMoves(int x, int y) {
84+
x += 310;
85+
y += 310;
86+
int ans = 0;
87+
Queue<int[]> q = new ArrayDeque<>();
88+
q.offer(new int[]{310, 310});
89+
boolean[][] vis = new boolean[700][700];
90+
vis[310][310] = true;
91+
int[][] dirs = {{-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}};
92+
while (!q.isEmpty()) {
93+
for (int k = q.size(); k > 0; --k) {
94+
int[] p = q.poll();
95+
if (p[0] == x && p[1] == y) {
96+
return ans;
97+
}
98+
for (int[] dir : dirs) {
99+
int c = p[0] + dir[0];
100+
int d = p[1] + dir[1];
101+
if (!vis[c][d]) {
102+
vis[c][d] = true;
103+
q.offer(new int[]{c, d});
104+
}
105+
}
106+
}
107+
++ans;
108+
}
109+
return -1;
110+
}
111+
}
112+
```
113+
114+
### **C++**
115+
116+
```cpp
117+
class Solution {
118+
public:
119+
int minKnightMoves(int x, int y) {
120+
x += 310;
121+
y += 310;
122+
int ans = 0;
123+
queue<pair<int, int>> q;
124+
q.push({310, 310});
125+
vector<vector<bool>> vis(700, vector<bool>(700));
126+
vis[310][310] = true;
127+
vector<vector<int>> dirs = {{-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}};
128+
while (!q.empty())
129+
{
130+
for (int k = q.size(); k > 0; --k)
131+
{
132+
auto p = q.front();
133+
q.pop();
134+
if (p.first == x && p.second == y) return ans;
135+
for (auto& dir : dirs)
136+
{
137+
int c = p.first + dir[0], d = p.second + dir[1];
138+
if (!vis[c][d])
139+
{
140+
vis[c][d] = true;
141+
q.push({c, d});
142+
}
143+
}
144+
}
145+
++ans;
146+
}
147+
return -1;
148+
}
149+
};
150+
```
64151
152+
### **Go**
153+
154+
```go
155+
func minKnightMoves(x int, y int) int {
156+
x, y = x+310, y+310
157+
ans := 0
158+
q := [][]int{{310, 310}}
159+
vis := make([][]bool, 700)
160+
for i := range vis {
161+
vis[i] = make([]bool, 700)
162+
}
163+
dirs := [][]int{{-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}}
164+
for len(q) > 0 {
165+
for k := len(q); k > 0; k-- {
166+
p := q[0]
167+
q = q[1:]
168+
if p[0] == x && p[1] == y {
169+
return ans
170+
}
171+
for _, dir := range dirs {
172+
c, d := p[0]+dir[0], p[1]+dir[1]
173+
if !vis[c][d] {
174+
vis[c][d] = true
175+
q = append(q, []int{c, d})
176+
}
177+
}
178+
}
179+
ans++
180+
}
181+
return -1
182+
}
65183
```
66184

67185
### **...**

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

Lines changed: 119 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -38,18 +38,136 @@
3838

3939
## Solutions
4040

41+
BFS.
42+
4143
<!-- tabs:start -->
4244

4345
### **Python3**
4446

4547
```python
46-
48+
class Solution:
49+
def minKnightMoves(self, x: int, y: int) -> int:
50+
q = deque([(0, 0)])
51+
ans = 0
52+
vis = set([(0, 0)])
53+
while q:
54+
for _ in range(len(q), 0, -1):
55+
i, j = q.popleft()
56+
if (i, j) == (x, y):
57+
return ans
58+
for a, b in [[-2, 1], [-1, 2], [1, 2], [2, 1], [2, -1], [1, -2], [-1, -2], [-2, -1]]:
59+
c, d = i + a, j + b
60+
if (c, d) not in vis:
61+
vis.add((c, d))
62+
q.append((c, d))
63+
ans += 1
64+
return -1
4765
```
4866

4967
### **Java**
5068

5169
```java
70+
class Solution {
71+
public int minKnightMoves(int x, int y) {
72+
x += 310;
73+
y += 310;
74+
int ans = 0;
75+
Queue<int[]> q = new ArrayDeque<>();
76+
q.offer(new int[]{310, 310});
77+
boolean[][] vis = new boolean[700][700];
78+
vis[310][310] = true;
79+
int[][] dirs = {{-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}};
80+
while (!q.isEmpty()) {
81+
for (int k = q.size(); k > 0; --k) {
82+
int[] p = q.poll();
83+
if (p[0] == x && p[1] == y) {
84+
return ans;
85+
}
86+
for (int[] dir : dirs) {
87+
int c = p[0] + dir[0];
88+
int d = p[1] + dir[1];
89+
if (!vis[c][d]) {
90+
vis[c][d] = true;
91+
q.offer(new int[]{c, d});
92+
}
93+
}
94+
}
95+
++ans;
96+
}
97+
return -1;
98+
}
99+
}
100+
```
101+
102+
### **C++**
103+
104+
```cpp
105+
class Solution {
106+
public:
107+
int minKnightMoves(int x, int y) {
108+
x += 310;
109+
y += 310;
110+
int ans = 0;
111+
queue<pair<int, int>> q;
112+
q.push({310, 310});
113+
vector<vector<bool>> vis(700, vector<bool>(700));
114+
vis[310][310] = true;
115+
vector<vector<int>> dirs = {{-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}};
116+
while (!q.empty())
117+
{
118+
for (int k = q.size(); k > 0; --k)
119+
{
120+
auto p = q.front();
121+
q.pop();
122+
if (p.first == x && p.second == y) return ans;
123+
for (auto& dir : dirs)
124+
{
125+
int c = p.first + dir[0], d = p.second + dir[1];
126+
if (!vis[c][d])
127+
{
128+
vis[c][d] = true;
129+
q.push({c, d});
130+
}
131+
}
132+
}
133+
++ans;
134+
}
135+
return -1;
136+
}
137+
};
138+
```
52139
140+
### **Go**
141+
142+
```go
143+
func minKnightMoves(x int, y int) int {
144+
x, y = x+310, y+310
145+
ans := 0
146+
q := [][]int{{310, 310}}
147+
vis := make([][]bool, 700)
148+
for i := range vis {
149+
vis[i] = make([]bool, 700)
150+
}
151+
dirs := [][]int{{-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}}
152+
for len(q) > 0 {
153+
for k := len(q); k > 0; k-- {
154+
p := q[0]
155+
q = q[1:]
156+
if p[0] == x && p[1] == y {
157+
return ans
158+
}
159+
for _, dir := range dirs {
160+
c, d := p[0]+dir[0], p[1]+dir[1]
161+
if !vis[c][d] {
162+
vis[c][d] = true
163+
q = append(q, []int{c, d})
164+
}
165+
}
166+
}
167+
ans++
168+
}
169+
return -1
170+
}
53171
```
54172

55173
### **...**

‎solution/1100-1199/1197.Minimum Knight Moves/Solution.cpp

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
class Solution {
2+
public:
3+
int minKnightMoves(int x, int y) {
4+
x += 310;
5+
y += 310;
6+
int ans = 0;
7+
queue<pair<int, int>> q;
8+
q.push({310, 310});
9+
vector<vector<bool>> vis(700, vector<bool>(700));
10+
vis[310][310] = true;
11+
vector<vector<int>> dirs = {{-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}};
12+
while (!q.empty())
13+
{
14+
for (int k = q.size(); k > 0; --k)
15+
{
16+
auto p = q.front();
17+
q.pop();
18+
if (p.first == x && p.second == y) return ans;
19+
for (auto& dir : dirs)
20+
{
21+
int c = p.first + dir[0], d = p.second + dir[1];
22+
if (!vis[c][d])
23+
{
24+
vis[c][d] = true;
25+
q.push({c, d});
26+
}
27+
}
28+
}
29+
++ans;
30+
}
31+
return -1;
32+
}
33+
};

‎solution/1100-1199/1197.Minimum Knight Moves/Solution.go

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
func minKnightMoves(x int, y int) int {
2+
x, y = x+310, y+310
3+
ans := 0
4+
q := [][]int{{310, 310}}
5+
vis := make([][]bool, 700)
6+
for i := range vis {
7+
vis[i] = make([]bool, 700)
8+
}
9+
dirs := [][]int{{-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}}
10+
for len(q) > 0 {
11+
for k := len(q); k > 0; k-- {
12+
p := q[0]
13+
q = q[1:]
14+
if p[0] == x && p[1] == y {
15+
return ans
16+
}
17+
for _, dir := range dirs {
18+
c, d := p[0]+dir[0], p[1]+dir[1]
19+
if !vis[c][d] {
20+
vis[c][d] = true
21+
q = append(q, []int{c, d})
22+
}
23+
}
24+
}
25+
ans++
26+
}
27+
return -1
28+
}

‎solution/1100-1199/1197.Minimum Knight Moves/Solution.java

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
class Solution {
2+
public int minKnightMoves(int x, int y) {
3+
x += 310;
4+
y += 310;
5+
int ans = 0;
6+
Queue<int[]> q = new ArrayDeque<>();
7+
q.offer(new int[]{310, 310});
8+
boolean[][] vis = new boolean[700][700];
9+
vis[310][310] = true;
10+
int[][] dirs = {{-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}};
11+
while (!q.isEmpty()) {
12+
for (int k = q.size(); k > 0; --k) {
13+
int[] p = q.poll();
14+
if (p[0] == x && p[1] == y) {
15+
return ans;
16+
}
17+
for (int[] dir : dirs) {
18+
int c = p[0] + dir[0];
19+
int d = p[1] + dir[1];
20+
if (!vis[c][d]) {
21+
vis[c][d] = true;
22+
q.offer(new int[]{c, d});
23+
}
24+
}
25+
}
26+
++ans;
27+
}
28+
return -1;
29+
}
30+
}

0 commit comments

Comments
 (0)