HackerRank KnightL on a Chessboard Problem Solution

HackerRank KnightL on a Chessboard Solution

Yashwant Parihar,

In this post, we will solve HackerRank KnightL on a Chessboard Problem Solution.

KnightL is a chess piece that moves in an L shape. We define the possible moves of Knight L(a, b) as any movement from some position (1, 1) to some (x2, y2) satisfying either of the following:
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 KnightL(1, 2) or KnightL(2, 1) can move to from its current location at the center of a 5 x 5 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 Knight L (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(a, b) according to the Output Format specified
    below.

Output Format
Print exactlyn – 1 lines of output in which each line i (where 1 < i < n) contains n 1 space-separated integers describing the minimum number of moves KnightL(i, j) must make for each respective j (where 1 <j<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

5

Sample Output 0

4 4 2 8
4 2 4 4
2 4 -1 -1
8 4 -1 1
HackerRank KnightL on a Chessboard Problem Solution
HackerRank KnightL on a Chessboard Problem Solution

KnightL on a Chessboard C Solution

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>


typedef struct
{
    int x;
    int y;
}coordinate;

unsigned char   **vectorMap;
//unsigned short  *dist;
//coordinate      *q;


int getNumberOfMove3(int x, int y, int dx, int dy, int n){
	coordinate 	q[1000];
	int 		dist[1000];
	int 		front = 0;
	int 		rear = 0;
	int			x1;
	int			y1;
	int 		x2;
	int			y2;
	int			move;
	coordinate 	possibleMove[8];

	q[rear].x = n-1;
	q[rear].y = n-1;
	dist[rear]=0;
	rear++;
	vectorMap[n-1][n-1] = 1;

	possibleMove[0].x = 1*dx;
	possibleMove[0].y = 1*dy;

	possibleMove[1].x = -1*dx;
	possibleMove[1].y = 1*dy;

	possibleMove[2].x = 1*dx;
	possibleMove[2].y = -1*dy;

	possibleMove[3].x = -1*dx;
	possibleMove[3].y = -1*dy;

	possibleMove[4].x = 1*dy;
	possibleMove[4].y = 1*dx;

	possibleMove[5].x = -1*dy;
	possibleMove[5].y = 1*dx;

	possibleMove[6].x = 1*dy;
	possibleMove[6].y = -1*dx;

	possibleMove[7].x = -1*dy;
	possibleMove[7].y = -1*dx;


	while(rear!=front){

		x1 = q[front].x;
		y1 = q[front].y;
		move = dist[front];
		front++;
		if(x1 == x && y1 == y)
			break;
		
		for(int i=0; i<8; i++){
			x2 = x1 + possibleMove[i].x;
			y2 = y1 + possibleMove[i].y;
			if(x2>=0 && x2<n && y2>=0 && y2<n && !vectorMap[x2][y2]){
				q[rear].x = x2;
				q[rear].y = y2;
				dist[rear] = move+1;
				rear++;		
				vectorMap[x2][y2] = 1;
			}
		}
	}
	if(x1 == x && y1 == y)
		return move+1;
	else
		return 0;
}

int main(){
    int n; 
    scanf("%d",&n);
    
	// your code goes here
    int cnt = 0;
    

	vectorMap = (unsigned char **)malloc(n*sizeof(unsigned char *));
	for(int i=0; i<n; i++){
		vectorMap[i] = (unsigned char *)malloc(n*sizeof(unsigned char));
	}
    
    //q = (coordinate *) malloc(n*sizeof(coordinate));
    //dist = (unsigned short *) malloc(n*sizeof(unsigned short));
	
	for(int i=1; i<n; i++)
    {
        for(int j=1; j<n; j++)
        {
			for(int k=0; k<n; k++)
				memset(vectorMap[k], 0, n);
				
            cnt = getNumberOfMove3(i, j, i-0, j-0, n);
            
            if(cnt)
                printf("%d ", cnt);
            else
                printf("-1 ");
        }
        printf("\n");
    }

	for(int i=0; i<n; i++){
		free(vectorMap[i]);
	}
	free(vectorMap);
    //free(q);
    //free(dist);
    return 0;
}

KnightL on a Chessboard C++ Solution

#include <bits/stdc++.h>
using namespace std;
int n;
int chk(int a)
{
    if(a>=1 && a<=n )
        return 1;
    return 0;
}
#define mp make_pair
int solve(int a,int b)
{
    vector<vector<int> > gp(n+1,vector<int>(n+1,0));
    queue<pair<int,int> > q;
    q.push(mp(1,1));
    q.push(mp(-1,-1));
    int l=0;
    while(!q.empty())
    {
        
        pair<int,int> p=q.front();
        q.pop();
        
        if(p.first==-1)
        {
            if(q.empty())
                break;
            l++;
            q.push(mp(-1,-1));
            
        }
        else
        {
            if(gp[p.first][p.second]==1)
                continue;
            gp[p.first][p.second]=1;
            if(p.first==p.second && p.first==n)
            {
                return l;
            }
            if(chk(p.first-a) && chk(p.second+b))
            {
                q.push(mp(p.first-a,p.second+b));
            }
            if(chk(p.first+a) && chk(p.second-b))
            {
                q.push(mp(p.first+a,p.second-b));
            }
            if(chk(p.first-a) && chk(p.second-b))
            {
                q.push(mp(p.first-a,p.second-b));
            }
            if(chk(p.first+a) && chk(p.second+b))
            {
                q.push(mp(p.first+a,p.second+b));
            }
            
            if(chk(p.first-b) && chk(p.second+a))
            {
                q.push(mp(p.first-b,p.second+a));
            }
            if(chk(p.first+b) && chk(p.second-a))
            {
                q.push(mp(p.first+b,p.second-a));
            }
            if(chk(p.first-b) && chk(p.second-a))
            {
                q.push(mp(p.first-b,p.second-a));
            }
            if(chk(p.first+b) && chk(p.second+a))
            {
                q.push(mp(p.first+b,p.second+a));
            }
        }
    }
    return -1;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin>>n;
    vector<vector<int> > v(n+1,vector<int>(n+1,0));
    for(int i=1;i<n;i++)
    {
        for(int j=i;j<n;j++)
        {
            v[i][j]=v[j][i]=solve(i,j);
        }
    }
    for(int i=1;i<n;i++)
    {
        for(int j=1;j<n;j++)
        {
            cout<<v[i][j]<<" ";
        }
        cout<<endl;
    }
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    return 0;
}

KnightL on a Chessboard C Sharp Solution

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution {

    static int n;
    
    static bool hasNewMarkedCells(int[,] prevDesk,int[,] currDesk){
        bool res = false;
        
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){ 
                if(prevDesk[i,j] == -1 && currDesk[i,j] > -1){
                    res = true;
                    break;
                }
            }
            if(res) break;
        }
        
        return res;
        
    }
    
    static void Main(String[] args) {
        n = Convert.ToInt32(Console.ReadLine());
              
        int[,] results = new int[n-1,n-1];
        for(int i=0;i<n-1;i++){
            for(int j=0;j<n-1;j++) results[i,j] = -1;
        }
        
        int[,] currDesk = new int[n,n];       
        int[,] prevDesk = currDesk.Clone() as int[,];
              
        for(int i=1;i<n;i++){
            for(int j=1;j<n;j++){
                for(int m=0;m<n;m++){
                    for(int p=0;p<n;p++) currDesk[m,p] = -1;
                }

                prevDesk = currDesk.Clone() as int[,];

                currDesk[0,0] = 0;
                
                int cnt = 0;
                
                //Console.WriteLine("i,j: " + i.ToString() + ", " +j.ToString());
                while(hasNewMarkedCells(prevDesk,currDesk) && results[i-1,j-1]<0){
                    prevDesk = currDesk.Clone() as int[,];
                    for(int k=0;k<n;k++){
                        for(int l=0;l<n;l++){
                             if(prevDesk[k,l]!=-1){
                                 if(k+i<n && l+j<n && prevDesk[k+i,l+j]==-1){
                                    currDesk[k+i,l+j] = prevDesk[k,l]+1; 
                                 } 
                                 if(k+i<n && l-j>=0 && prevDesk[k+i,l-j]==-1){
                                     currDesk[k+i,l-j] = prevDesk[k,l]+1;
                                 } 
                                 if(k-i>=0 && l+j<n && prevDesk[k-i,l+j]==-1){
                                     currDesk[k-i,l+j] = prevDesk[k,l]+1;
                                 } 
                                 if(k-i>=0 && l-j>=0 && prevDesk[k-i,l-j]==-1){
                                     currDesk[k-i,l-j] = prevDesk[k,l]+1;
                                 } 
                                
                                 if(k+j<n && l+i<n && prevDesk[k+j,l+i]==-1){
                                    currDesk[k+j,l+i] = prevDesk[k,l]+1; 
                                 } 
                                 if(k+j<n && l-i>=0 && prevDesk[k+j,l-i]==-1){
                                     currDesk[k+j,l-i] = prevDesk[k,l]+1;
                                 } 
                                 if(k-j>=0 && l+i<n && prevDesk[k-j,l+i]==-1){
                                     currDesk[k-j,l+i] = prevDesk[k,l]+1;
                                 } 
                                 if(k-j>=0 && l-i>=0 && prevDesk[k-j,l-i]==-1){
                                     currDesk[k-j,l-i] = prevDesk[k,l]+1;
                                 } 
                             }  
                        }
                    }
                    
                    results[i-1,j-1] = currDesk[n-1,n-1];
                }

                Console.Write(results[i-1,j-1].ToString() + " ");
                
                cnt++;
            }
            
            Console.WriteLine();
        }
        
    }
}

KnightL on a Chessboard Java Solution

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {
    
    
    static int[][] board;
    static int n;
    static int[][] directions = {{1,1},{1,-1},{-1,-1},{-1,1}};
    static int[][] result;
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        
        
        // your code goes here
        board = new int[n][n];
        result = new int[n - 1][n - 1];
        for (int[] row : result) {
            Arrays.fill(row, -1);
        }
        for (int i = 1; i < n; i++) {
            for (int j = i; j < n; j++) {
                // consider pair (i,j) 
                // fill board
                for (int[] row : board) {
                    Arrays.fill(row, -1);
                }
                
                board[0][0] = 0;
                //do DFS
                Queue<Coor> queue = new ArrayDeque<>();
                queue.add(new Coor(0, 0));
                while (!queue.isEmpty()) {
                    Coor cur = queue.remove();
                    for (int[] dir : directions) {
                        Coor next = new Coor(cur.x + dir[0] * i, cur.y + dir[1] * j); // i,j
                        if (isValid(next) && board[next.x][next.y] == -1) {
                            board[next.x][next.y] = board[cur.x][cur.y] + 1; // add 1 step
                            queue.add(next);
                        }
                        next =  new Coor(cur.x + dir[0] * j, cur.y + dir[1] * i); // j,i
                        if (isValid(next) && board[next.x][next.y] == -1) {
                            board[next.x][next.y] = board[cur.x][cur.y] + 1; // add 1 step
                            queue.add(next);
                        }
                    }
                    if (board[n - 1][n - 1] != -1) {
                        result[i - 1][j - 1] = board[n - 1][n - 1];
                        result[j - 1][i - 1] = result[i - 1][j - 1];
                        break;
                    }
                }
            }
        }
        
        for (int i = 0; i < result.length; i++) {
            for (int j = 0; j < result.length; j++) {
                System.out.print(result[i][j]);
                if (j != result.length - 1) {
                    System.out.print(" ");
                }
            }
            System.out.print("\n");
        }
    }
    
    private static boolean isValid(Coor c) {
        return c.x >= 0 && c.x < n && c.y >= 0 && c.y < n;
    }
    
    private static class Coor {
        int x;
        int y;
        public Coor(int xx, int yy) {
            x = xx;
            y = yy;
        }
    }
}

KnightL on a Chessboard JavaScript Solution

process.stdin.resume();
process.stdin.setEncoding('ascii');

var input_stdin = "";
var input_stdin_array = "";
var input_currentline = 0;

process.stdin.on('data', function (data) {
    input_stdin += data;
});

process.stdin.on('end', function () {
    input_stdin_array = input_stdin.split("\n");
    main();    
});

function readLine() {
    return input_stdin_array[input_currentline++];
}

/////////////// ignore above this line ////////////////////

var table = {};

function resettable(n) {
    for(var i=1;i<=n;i++)
        table[i] = {};
    table[1][1] = 0;
}

function outputtable(n) {
    for(var y=1;y<=n;y++) {
        var row = []
        for(var x=1;x<=n;x++)
            row.push(table[y][x]);
        console.log(row.join(" "));
    }
}

function checkpos(n, move, xpos, ypos) {
    if ((xpos > 0) && (xpos <= n) && (ypos > 0) && (ypos <= n) && (!(xpos in table[ypos]))) {
        table[ypos][xpos] = move;
        return true;
    }
    return false;
}

function performmoves(n, move, xpos, ypos, xjump, yjump) {
    var changed = false;
    changed = checkpos(n, move, xpos+xjump, ypos+yjump) || changed;
    changed = checkpos(n, move, xpos+xjump, ypos-yjump) || changed;
    changed = checkpos(n, move, xpos-xjump, ypos+yjump) || changed;
    changed = checkpos(n, move, xpos-xjump, ypos-yjump) || changed;
    if (xjump != yjump) {
        changed = checkpos(n, move, xpos+yjump, ypos+xjump) || changed;
        changed = checkpos(n, move, xpos+yjump, ypos-xjump) || changed;
        changed = checkpos(n, move, xpos-yjump, ypos+xjump) || changed;
        changed = checkpos(n, move, xpos-yjump, ypos-xjump) || changed;
    }
    return changed;
}

function calcmoves(n, xjump, yjump) {
    resettable(n);
    var changed = true;
    var move = 0;
    while (changed) {
        changed = false;
        for(var y=1;y<=n;y++)
            for (var x=1;x<=n;x++)
                if ((x in table[y]) && (table[y][x] == move)) {
                    changed = performmoves(n, move+1, x, y, xjump, yjump) || changed;
                }
        move++;
        if (n in table[n])
            return table[n][n];
    }
    return -1;
}

function main() {
    var n = parseInt(readLine());
    // your code goes here
    for(var yjump=1;yjump<n;yjump++) {
        var moves = [];
        for(var xjump=1;xjump<n;xjump++)
            moves.push(calcmoves(n, xjump, yjump));
        console.log(moves.join(" "));
     }
}

KnightL on a Chessboard Python Solution

#!/bin/python3

def pos_moves(x,y,a,b,n):
    result=[]
    for xd,yd in ((a,b),(a,-b),(-a,b),(-a,-b),(b,a),(b,-a),(-b,a),(-b,-a)):
        if (not 0 <= x+xd < n) or (not 0 <= y+yd < n):
            continue
        result.append((x+xd,y+yd))
    return result

def moves(a,b,n):
    found=set()
    d={(0,0):0}
    todo=[(0,0)]
    goal=(n-1,n-1)
    while todo:
        p = todo.pop(0)
        d_p=d[p]
        for m in pos_moves(p[0],p[1],a,b,n):
            if m in found:continue
            elif m == goal:return d_p+1
            else:
                found.add(m)
                d[m] = d_p+1
                todo.append(m)
    return -1
        

n = int(input().strip())
for i in range(1,n):
    print(*[moves(i,j,n) for j in range(1,n)])
c C# C++ HackerRank Solutions java javascript python

Leave a Reply