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])))

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];
                Queue<Point> queue = new LinkedList<>();
                queue.add(new Point(0, 0, 0));
                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();
            }
        }
    }
}

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;
}

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>

char* readline();

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;
    char* n_str = readline();
    int n = strtol(n_str, &n_endptr, 10);

    if (n_endptr == n_str || *n_endptr != '') { 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;
}

char* readline() {
    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] = '';
    }

    data = realloc(data, data_length);

    return data;
}