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 != '\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;
}
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] = '\0';
}
data = realloc(data, data_length);
return data;
}
0 Comments