# HackerRank KnightL on a Chessboard problem solution

In this HackerRank KnightL on a Chessboard problem solution we have 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(a,b) according to the Output Format specified below.

## Problem solution in Python.

```import sys
n = int(input().strip())

def allmoves(i,j,a,b,n):
moves=[]
deltas=[(a,b),(a,-b),(-a,b),(-a,-b)]
deltas.extend([(b,a),(b,-a),(-b,a),(-b,-a)])
for delta in deltas:
if i+delta[0]>=0 and i+delta[0]<n and j+delta[1]>=0 and j+delta[1]<n:
moves.append((i+delta[0],j+delta[1]))
return moves

def finddist(n,a,b):
dist=[[-1 for x in range(n)] for x in range(n)]
dist[n-1][n-1]=0
todo=[(n-1,n-1)]
while len(todo)>0:
(i,j)=todo.pop(0)
newmoves=allmoves(i,j,a,b,n)
for move in newmoves:
if dist[move[0]][move[1]]==-1:
dist[move[0]][move[1]]=dist[i][j]+1
todo.append((move[0],move[1]))
if move[0]==0 and move[1]==0:
break
return dist[0][0]

ans=[[0 for x in range(n-1)] for x in range(n-1)]
for i in range(n-1):
for j in range(n-1):
ans[i][j]=finddist(n,i+1,j+1)
for i in range(n-1):
print(' '.join(map(str,ans[i])))
```

{"mode":"full","isActive":false}

## Problem solution in Java.

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

public class Solution {

static class Point {
int x;
int y;
int turn;
Point(int x,  int y, int turn) {
this.x = x;
this.y = y;
this.turn = turn;
}

}

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();

int[][] result = new int[n][n];
for (int a = 1; a < n; a++) {
for (int b = 1; b < n; b++) {
if (result[b][a] != 0) {
System.out.print(result[b][a]);
if (b < n - 1)
System.out.print(" ");
} else {
boolean[][] visited = new boolean[n][n];
visited[0][0] = true;

boolean hit = false;
while (!queue.isEmpty()) {
Point pt = queue.poll();

int x = pt.x - a;
int y = pt.y - b;
if (x >= 0 && y >= 0 && !visited[x][y]) {
if (x == n - 1 && y == n - 1) {
System.out.print(pt.turn + 1);
hit = true;
result[a][b] = pt.turn + 1;
if (b < n - 1)
System.out.print(" ");
break;
} else {
visited[x][y] = true;
queue.add(new Point(x, y, pt.turn + 1));
}
}

x = pt.x + a;
y = pt.y - b;
if (x < n && y >= 0 && !visited[x][y]) {
if (x == n - 1 && y == n - 1) {
System.out.print(pt.turn + 1);
hit = true;
result[a][b] = pt.turn + 1;
if (b < n - 1)
System.out.print(" ");
break;
} else {
visited[x][y] = true;
queue.add(new Point(x, y, pt.turn + 1));
}
}

x = pt.x - a;
y = pt.y + b;
if (x >= 0 && y < n && !visited[x][y]) {
if (x == n - 1 && y == n - 1) {
System.out.print(pt.turn + 1);
hit = true;
result[a][b] = pt.turn + 1;
if (b < n - 1)
System.out.print(" ");
break;
} else {
visited[x][y] = true;
queue.add(new Point(x, y, pt.turn + 1));
}
}

x = pt.x + a;
y = pt.y + b;
if (x < n && y < n && !visited[x][y]) {
if (x == n - 1 && y == n - 1) {
System.out.print(pt.turn + 1);
hit = true;
result[a][b] = pt.turn + 1;
if (b < n - 1)
System.out.print(" ");
break;
} else {
visited[x][y] = true;
queue.add(new Point(x, y, pt.turn + 1));
}
}

x = pt.x - b;
y = pt.y - a;
if (x >= 0 && y >= 0 && !visited[x][y]) {
if (x == n - 1 && y == n - 1) {
System.out.print(pt.turn + 1);
hit = true;
result[a][b] = pt.turn + 1;
if (b < n - 1)
System.out.print(" ");
break;
} else {
visited[x][y] = true;
queue.add(new Point(x, y, pt.turn + 1));
}
}

x = pt.x + b;
y = pt.y - a;
if (x < n && y >= 0 && !visited[x][y]) {
if (x == n - 1 && y == n - 1) {
System.out.print(pt.turn + 1);
hit = true;
result[a][b] = pt.turn + 1;
if (b < n - 1)
System.out.print(" ");
break;
} else {
visited[x][y] = true;
queue.add(new Point(x, y, pt.turn + 1));
}
}

x = pt.x - b;
y = pt.y + a;
if (x >= 0 && y < n && !visited[x][y]) {
if (x == n - 1 && y == n - 1) {
System.out.print(pt.turn + 1);
hit = true;
result[a][b] = pt.turn + 1;
if (b < n - 1)
System.out.print(" ");
break;
} else {
visited[x][y] = true;
queue.add(new Point(x, y, pt.turn + 1));
}
}

x = pt.x + b;
y = pt.y + a;
if (x < n && y < n && !visited[x][y]) {
if (x == n - 1 && y == n - 1) {
System.out.print(pt.turn + 1);
hit = true;
result[a][b] = pt.turn + 1;
if (b < n - 1)
System.out.print(" ");
break;
} else {
visited[x][y] = true;
queue.add(new Point(x, y, pt.turn + 1));
}
}
}
if (!hit) {
result[a][b] = -1;
System.out.print("-1");
if (b < n - 1)
System.out.print(" ");
}
}
}
if (a < n - 1) {
System.out.println();
}
}
}
}
```

{"mode":"full","isActive":false}

## Problem solution in C++.

```#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <functional>
#include <algorithm>
#include <cmath>
#include <climits>

using namespace std;

#define mp(first, second) make_pair(first, second)

typedef unsigned long long ul;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;

int n;
vector<vi> ansMatrix;
vector<vi> chessBoard;

void tryAdd(int tRow, int tCol, int pRow, int pCol, queue<ii> &q)
{
if (tRow < 0 || tRow >= chessBoard.size() || tCol < 0 || tCol >= chessBoard[0].size() || chessBoard[tRow][tCol] != 0)
{
return;
}

chessBoard[tRow][tCol] = chessBoard[pRow][pCol] + 1;
q.push(mp(tRow, tCol));
}

void bfs(int sRow, int sCol)
{
queue<ii> q;
q.push(mp(0, 0));
++sRow; ++sCol;

int dx[] = {-sRow, -sRow, +sRow, +sRow, -sCol, -sCol, +sCol, +sCol};
int dy[] = {-sCol, +sCol, -sCol, +sCol, -sRow, +sRow, +sRow, -sRow};

while (!q.empty())
{
ii curr = q.front();
q.pop();

for (size_t i = 0; i < 8; i++)
{
tryAdd(curr.first + dx[i], curr.second + dy[i], curr.first, curr.second, q);
}
}

if (chessBoard[n - 1][n - 1] != 0)
{
ansMatrix[sRow - 1][sCol - 1] = chessBoard[n - 1][n - 1];
}
else
{
ansMatrix[sRow - 1][sCol - 1] = -1;
}

chessBoard.clear();
chessBoard.resize(n, vi(n, 0));
}

int main()
{
cin.tie(nullptr);
ios_base::sync_with_stdio(false);

cin >> n;
ansMatrix.resize(n - 1, vi(n - 1, -1));
chessBoard.resize(n, vi(n, 0));

for (size_t i = 0; i < n - 1; i++)
{
for (size_t j = 0; j < n - 1; j++)
{
bfs(i, j);
}
}

for (int i = 0; i < ansMatrix.size(); i++)
{
for (int j = 0; j < ansMatrix[0].size(); j++)
{
cout << ansMatrix[i][j] << " ";
}
cout << endl;
}

return 0;
}```

{"mode":"full","isActive":false}

## Problem solution in C.

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

int min_move(int n, int a, int b){
int queue_x[5000], queue_y[5000];
int queue_front = 0, queue_back = 0;
int table[25][25];
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
table[i][j] = -1;
}
}
table[0][0] = 0;
queue_x[queue_back] = 0;
queue_y[queue_back] = 0;
queue_back++;

while(queue_back != queue_front){
int pos_x = queue_x[queue_front];
int pos_y = queue_y[queue_front];
queue_front++;

int d_x[8], d_y[8];
d_x[0] =  a; d_y[0] =  b;
d_x[1] =  a; d_y[1] = -b;
d_x[2] =  b; d_y[2] =  a;
d_x[3] =  b; d_y[3] = -a;
d_x[4] = -a; d_y[4] =  b;
d_x[5] = -a; d_y[5] = -b;
d_x[6] = -b; d_y[6] =  a;
d_x[7] = -b; d_y[7] = -a;
for(int i=0; i<8; i++){
int next_x = pos_x + d_x[i];
int next_y = pos_y + d_y[i];
if(0 <= next_x && next_x < n && 0 <= next_y && next_y < n){
if(table[next_x][next_y] == -1){
table[next_x][next_y] = table[pos_x][pos_y] + 1;
queue_x[queue_back] = next_x;
queue_y[queue_back] = next_y;
queue_back++;
}
}
}
}
return table[n-1][n-1];
}

int** knightlOnAChessboard(int n, int* result_rows, int* result_columns) {
*result_rows = *result_columns = n - 1;
int **result = malloc(sizeof(int*) * (*result_rows));
for(int i=0; i<*result_rows; i++){
result[i] = malloc(sizeof(int) * (*result_columns));
for(int j=0; j<*result_columns; j++){
result[i][j] = min_move(n, i+1, j+1);
}
}
return result;
}

int main()
{
FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w");

char* n_endptr;
int n = strtol(n_str, &n_endptr, 10);

if (n_endptr == n_str || *n_endptr != '\0') { exit(EXIT_FAILURE); }

int result_rows;
int result_columns;
int** result = knightlOnAChessboard(n, &result_rows, &result_columns);

for (int i = 0; i < result_rows; i++) {
for (int j = 0; j < result_columns; j++) {
fprintf(fptr, "%d", *(*(result + i) + j));

if (j != result_columns - 1) {
fprintf(fptr, " ");
}
}

if (i != result_rows - 1) {
fprintf(fptr, "\n");
}
}

fprintf(fptr, "\n");

fclose(fptr);

return 0;
}

size_t alloc_length = 1024;
size_t data_length = 0;
char* data = malloc(alloc_length);

while (true) {
char* cursor = data + data_length;
char* line = fgets(cursor, alloc_length - data_length, stdin);

if (!line) { break; }

data_length += strlen(cursor);

if (data_length < alloc_length - 1 || data[data_length - 1] == '\n') { break; }

size_t new_length = alloc_length << 1;
data = realloc(data, new_length);

if (!data) { break; }

alloc_length = new_length;
}

if (data[data_length - 1] == '\n') {
data[data_length - 1] = '\0';
}

data = realloc(data, data_length);

return data;
}
```

{"mode":"full","isActive":false}