priyansh2

Untitled

Dec 1st, 2020
536
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. bool check(int i ,int j,int n){
  2.     if(i>=0 && i<=n-1 && j>=0 && j<=n-1) return true;
  3.     return false;
  4. }
  5. int minStepToReachTarget(int knightPos[], int targetPos[], int N) {
  6.     vector<vector<int>> visit(N,vector<int>(N,-1));
  7.     queue<pair<pair<int ,int>,int>> q;
  8.     visit[knightPos[0]-1][knightPos[1]-1]=0;
  9.     q.push({{knightPos[0]-1,knightPos[1]-1},0});
  10.     int steps=0;
  11.     vector<pair<int,int>> dir = {{1,2},{-1,-2},{-2,-1},{-2,2},{-1,2},{1,2},{2,1},{2,-1}};
  12.     while(!q.empty()){
  13.         pair<pair<int,int>,int> p = q.front();
  14.         q.pop();
  15.         if(p.first==make_pair(targetPos[0]-1,targetPos[1]-1)){
  16.             steps = p.second;
  17.             break;
  18.            
  19.         }
  20.         for(auto x:dir){
  21.             pair<int,int> cor = make_pair(p.first.first + x.first,p.first.second + x.second);
  22.             if (visit[cor.first][cor.second]==-1 && check(cor.first,cor.second,N)){
  23.                 visit[cor.first][cor.second]=0;
  24.                 q.push(make_pair(cor,p.second+1));
  25.             }
  26.         }
  27.     }
  28.     return steps;
  29.    
  30. }
RAW Paste Data