hello_world/knight_on_chess_board.cpp at master · basant-kumar/hello_world · GitHub

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<iostream>
#include<queue>
#include<utility>
#include<map>

#define pb push_back
#define ff first
#define ss second
#define mpa make_pair
using namespace std;
typedef long long LL;

using namespace std;

int dx[8] = {2, 2, -2, -2, 1, 1, -1, -1};
int dy[8] = {-1, 1, 1, -1, 2, -2, 2, -2};

bool valid(int x, int y, int N, int M) {
    if(x <= 0 || y <= 0 || x > N || y > M)
            return false;
    return true;
}
int bfs(pair<int, int> p1, pair<int, int> p2, pair<int, int> p3) {

	int N = p3.ff;
    int M = p3.ss;
    queue<pair<pair<int, int>, int> > Que;
    map<pair<int, int>, bool> Vis;

    Que.push(mpa(p1, 0));

    while(!Que.empty()) {

	    pair<pair<int, int>, int> temp = Que.front();
	    Que.pop();

        if(temp.ff.ff == p2.ff && temp.ff.ss == p2.ss)
                return temp.ss;
        int x = temp.ff.ff;
        int y = temp.ff.ss;
        int dis = temp.ss + 1;


        if(Vis.count(mpa(x, y))){
            continue;
        }
        Vis[mpa(x, y)] = true;

        for(int i = 0; i < 8; ++i) {

		    int x1 = x + dx[i];
            int y1 = y + dy[i];
            if(valid(x1, y1, N, M))
            Que.push(mpa(mpa(x1, y1), dis));
        }

    }

    return -1;
}


int min_step_to_reach(pair<int, int> &source, pair<int, int> &dest, pair<int, int> &size){
	int ans=bfs(source, dest, size);
	return ans;
}


int main(){
	int N=6,M=6;
	pair<int, int> source, dest, size;
	source=make_pair(4, 5);
	dest=make_pair(1, 1);
	size=make_pair(N,M);

	cout<<min_step_to_reach(source, dest, size)<<endl;

	return 0;
}