C Programming(interview)

Question

Write an algorithm of the given problem

Given a chess board of order NxM and source points (s1,s2) and destination points (d1,d2), Your task to find min number of moves required by the Knight to go to the destination cell.

Comments

No, DFS cannot search minimum path.

BFS would be more perfect

---

@srestha,i understood that DFS wont give min path but can you pls explain how BFS will be efficient??

---

because in BFS we visit each child

in DFS it goes to maximum depth

Answer 1

Assume this problem as searching in graph where each block of chess board is vertex.
Define edges in such a graph and the ways when can you travel from vertex i to vertex j. Once we have the graph, then it reduces to finding the shortest path in an unweighted graph.

A knight can move to 8 positions from (x,y). 

(x, y) -> 
    (x + 2, y + 1)  
    (x + 2, y - 1)
    (x - 2, y + 1)
    (x - 2, y - 1)
    (x + 1, y + 2)
    (x + 1, y - 2)
    (x - 1, y + 2)
    (x - 1, y - 2)

Corresponding to the knight's move, we can define edges. 
(x,y) will have an edge to the 8 neighbors defined above. 

To find the shortest path, we just run a plain BFS. 

 

?

#include<bits/stdc++.h> #define pb push_back #define ff first #define ss second #define mpa make_pair using namespace std; typedef long long LL;   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 solve(int N, int M, int x1, int y1, int x2, int y2) {       pair<int, int> p1;     p1.ff = x1;     p1.ss = y1;       pair<int, int> p2;     p2.ff = x2;     p2.ss = y2;       pair<int, int> p3;     p3.ff = N;     p3.ss = M;       int ans = bfs(p1, p2, p3);     return ans; }   int main() {           cout << solve(8, 8, 1, 1, 8, 8) << endl;     return 0; }

I think this can help u