HackerRank KnightL on a Chessboard Solution
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
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)])
