-
Notifications
You must be signed in to change notification settings - Fork 0
/
Steps by Knight
45 lines (39 loc) · 1.38 KB
/
Steps by Knight
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<bits/stdc++.h>
using namespace std;
int main(){
int N, a, b, c;
cin>>N>>a>>b>>c;
int knightPos[] = {a, b};
int targetPos[] = {c, d};
cout<< minStepToReachTarget(knightPos, targetPos, N);
}
int minStepToReach(int knightX, int knightY, int targetX, int targetY, int N) {
if (knightX == targetX && knightY == targetY) return 0;
int visited[N + 1][N + 1] = {0};
visited[knightX][knightY] = 1;
queue<pair<int, int> > q;
//q.push(pair<int, int>(knightX, knightY));
q.push({knightX, knightY});
int rr[8] = {-2, -2, -1, -1, 1, 1, 2, 2};
int cc[8] = {-1, 1, -2, 2, -2, 2, -1, 1};
//travelling bfs to find all position a knight can take
while (!q.empty()) {
int r = q.front().first;
int c = q.front().second;
q.pop();
for (int i = 0; i < 8; i++) {
int nextr = r + rr[i];
int nextc = c + cc[i];
if (nextr < 1 || nextc < 1 || nextr > N || nextc > N) continue;
if (visited[nextr][nextc] != 0) continue;
if (nextr == targetX && nextc == targetY)
return visited[r][c];
visited[nextr][nextc] = visited[r][c] + 1;
q.push(pair<int, int>(nextr, nextc));
}
}
//return visited[targetX][targetY] - 1;
}
int minStepToReachTarget(int k[], int T[], int n){
return minStepToReach(k[0], k[1], T[0], T[1], n);
}