KnightL on a Chessboard

Published in

Codebrace

5 min readFeb 21, 2017

Problem Link: KnightL on a Chessboard

KnightL is a chess piece that moves in an L shape. We define the possible moves of KnightL(a,b) as any movement from some position (x1,y1) to some (x2,y2) to some satisfying either of the following:

* x2 = x1 ± and a, y2 = y1 ± and b or
* x2 = x1 ± +b and , or y2 = y1 ± a

Note that (a,b) and (b,a) allow for the same exact set of movements. For example, the diagram below depicts the possible locations that KinightL(1,2) or Knight(2,1) can move to from its current location at the center of 5 x 5 a chessboard:

Observe that for each possible movement, the Knight moves 2 units in one direction (i.e., horizontal or vertical) and 1 unit in the perpendicular direction.

Given the value of n for an n x n chessboard, answer the following question for each (a,b) pair where 1 <= a,b < n:

What is the minimum number of moves it takes for KnightL(a,b) to get from position (0,0) to position (n-1,n-1) ? If it’s not possible for the Knight to reach that destination, the answer is -1 instead.

Then print the answer for each KnightL according to the Output Format specified below.

Input Format

A single integer denoting .

Constraints

5 ≤ n ≤ 25

Output Format

Print exactly n-1 lines of output in which each line i (where 1 ≤ i < n ) n-1 contains space-separated integers describing the minimum number of moves KnightL(i,j) must make for each respective j (where 1 ≤ i < n ). If some KnightL(i,j) cannot reach position (n-1,n-1), print -1 instead.

For example, if n=3 we organize the answers for all the (i,j) pairs in our output like this:

(1,1) (1,2)
(2,1) (2,2)

Sample Input 0

Sample Output 0

Explanation 0

The diagram below depicts possible minimal paths for

One minimal path for

(0,0) -> (1,4) -> (2,0) -> (3,4) -> (4,0) -> (0,1) ->(4,2) -> (0,3) -> (4,4)

We then print 4 4 2 8 as our first line of output because KnightL(1,1) took 4 moves, KnightL(1,2) took 4 moves, KnightL(1,3) took 8 moves.

In some of the later rows of output, it’s impossible for KnightL(i,j) reach position (4,4). For example, KnightL(3,3) can only move back and forth between (0,0) and (3,3) so it will never reach (4,4).

SOLUTION

We need to run breadth first search for the graph by considering every block as a vertex and every move as an edge.

But i have tried a different approach here, i have done this problem by DP.

Process for all type of move. Start from (n-1, n-1) and break when it reached to (0,0) break the loop or if all approachable block are processed then answer will be -1. For this using a queue push all the approachable block and then dequeue one by one and enqueue the new approachable block and keep checking for the above mentioned condition.

See the commented code. It will make you understand better.

CODE

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;int main()
{
 int n; cin>>n;
 int op[n-1][n-1];
 bool isProcessed[n][n]; // to check if all the dequed block is processed or notfor(int k=1;k<=n-1;k++) // for a
 {
 for(int l=k;l<=n-1;l++) // for b
 {
 //cout<<"k="<<k<<" l="<<l<<endl;
 int a[n][n];
 for(int i=0;i<n;i++) // initialization
 for(int j=0;j<n;j++)
 a[i][j]=0;int count[n][n];
 for(int i=0;i<n;i++)
 for(int j=0;j<n;j++)
 count[i][j]=0;for(int i=0;i<n;i++)
 for(int j=0;j<n;j++)
 isProcessed[i][j]=false;queue< pair<int,int> > qu; // pushing the last block
 qu.push(make_pair(n-1,n-1));
 isProcessed[n-1][n-1]=true;
 ////cout<<qu.size();
 int x,y;
 int _count;
// running the loop till the queue is empty or the loop break insidewhile(qu.size()!=0)
 {
 x = qu.front().first;
 y = qu.front().second;
 a[x][y] = 1;
 _count = count[x][y];
 //cout<<"x= "<<x<<" y= "<<y<<endl;
 qu.pop();
 //cout<<qu.size()<<endl;
 int p,q;// pushing all the eight approachable block
 p = x+k;
 q = y+l;
 if(p>=0 && q>=0 && p<n && q<n) // checking if it is valid block
 {
 if(a[p][q]!=0) // is pushed already or not
 count[p][q] = min(count[p][q],_count+1);else
 {
 count[p][q] = _count+1;
 if(p==0 && q==0) { a[0][0]=1; break; }
 //cout<<"p= "<<p<<" q= "<<q<<endl;
 if(isProcessed[p][q]==false)
 {
 qu.push(make_pair(p,q));
 isProcessed[p][q]=true;
 }
 }
 }p = x+k;
 q = y-l;
 if(p>=0 && q>=0 && p<n && q<n)
 {
 if(a[p][q]!=0)
 count[p][q] = min(count[p][q],_count+1);
 else
 {
 count[p][q] = _count+1;
 if(p==0 && q==0) { a[0][0]=1; break; }//cout<<"p= "<<p<<" q= "<<q<<endl;
 if(isProcessed[p][q]==false)
 {
 qu.push(make_pair(p,q));
 isProcessed[p][q]=true;
 }
 }
 }p = x-k;
 q = y+l;
 if(p>=0 && q>=0 && p<n && q<n)
 {
 if(a[p][q]!=0)
 count[p][q] = min(count[p][q],_count+1);
 else
 {
 count[p][q] = _count+1;
 if(p==0 && q==0) { a[0][0]=1; break; }//cout<<"p= "<<p<<" q= "<<q<<endl;
 if(isProcessed[p][q]==false)
 {
 qu.push(make_pair(p,q));
 isProcessed[p][q]=true;
 }
 }
 }p = x-k;
 q = y-l;
 if(p>=0 && q>=0 && p<n && q<n)
 {
 if(a[p][q]!=0)
 count[p][q] = min(count[p][q],_count+1);
 else
 {
 count[p][q] = _count+1;
 if(p==0 && q==0) { a[0][0]=1; break; }//cout<<"p= "<<p<<" q= "<<q<<endl;
 if(isProcessed[p][q]==false)
 {
 qu.push(make_pair(p,q));
 isProcessed[p][q]=true;
 }
 }
 }p = x+l;
 q = y+k;
 if(p>=0 && q>=0 && p<n && q<n)
 {
 if(a[p][q]!=0)
 count[p][q] = min(count[p][q],_count+1);
 else
 {
 count[p][q] = _count+1;
 if(p==0 && q==0) { a[0][0]=1; break; }//cout<<"p= "<<p<<" q= "<<q<<endl;
 if(isProcessed[p][q]==false)
 {
 qu.push(make_pair(p,q));
 isProcessed[p][q]=true;
 }
 }
 }p = x+l;
 q = y-k;
 if(p>=0 && q>=0 && p<n && q<n)
 {
 if(a[p][q]!=0)
 count[p][q] = min(count[p][q],_count+1);
 else
 {
 count[p][q] = _count+1;
 if(p==0 && q==0) { a[0][0]=1; break; }//cout<<"p= "<<p<<" q= "<<q<<endl;
 if(isProcessed[p][q]==false)
 {
 qu.push(make_pair(p,q));
 isProcessed[p][q]=true;
 }
 }
 }p = x-l;
 q = y+k;
 if(p>=0 && q>=0 && p<n && q<n)
 {
 if(a[p][q]!=0)
 count[p][q] = min(count[p][q],_count+1);
 else
 {
 count[p][q] = _count+1;
 if(p==0 && q==0) { a[0][0]=1; break; }//cout<<"p= "<<p<<" q= "<<q<<endl;
 if(isProcessed[p][q]==false)
 {
 qu.push(make_pair(p,q));
 isProcessed[p][q]=true;
 }
 }
 }p = x-l;
 q = y-k;
 if(p>=0 && q>=0 && p<n && q<n)
 {
 if(a[p][q]!=0)
 count[p][q] = min(count[p][q],_count+1);
 else
 {
 count[p][q] = _count+1;
 if(p==0 && q==0) { a[0][0]=1; break; }
 //cout<<"p= "<<p<<" q= "<<q<<endl;
 count[p][q]=min(count[p][q],_count+1);
 if(isProcessed[p][q]==false)
 {
 qu.push(make_pair(p,q));
 isProcessed[p][q]=true;
 }
 }
 }
 /*if(k==1 && l==2) {
 for(int i=n-1;i>=0;i--) {
 for(int j=0;j<n;j++)
 cout<<count[j][i]<<" ";
 cout<<endl;
 } }
 cout<<endl;*/}
 /*for(int i=n-1;i>=0;i--) {
 for(int j=0;j<n;j++)
 //cout<<count[j][i]<<" ";
 //cout<<endl;
 }*/int ans=-1;if(a[0][0]==1) ans = count[x][y]+1; //if (0,0) is approached set the ans otherwise it will be -1
 op[k-1][l-1] = ans ;
 op[l-1][k-1] = ans ;
 }}
 for(int i=0;i<n-1;i++)
 {
 for(int j=0;j<n-1;j++)
 cout<<op[i][j]<<" ";
 cout<<endl;
 }
}

KnightL on a Chessboard

SOLUTION

CODE

Written by Ashish Patel