In this HackerRank Red Knight's Shortest Path problem solution we have given the coordinates of the starting position of the red knight and the coordinates of the destination, print the minimum number of moves that the red knight has to make in order to reach the destination and after that, print the order of the moves that must be followed to reach the destination in the shortest way. If the destination cannot be reached, print only the word "Impossible".
Problem solution in Python.
#!/bin/python3
import sys
def printShortestPath(n, i_start, j_start, i_end, j_end):
# Print the distance along with the sequence of moves.
diff_i = i_end - i_start
diff_j = j_end - j_start
i = i_start
j = j_start
if diff_i % 2 == 1:
print('Impossible')
return
if diff_i % 4 == 0 and diff_j % 2 == 1:
print('Impossible')
return
if diff_i % 4 == 2 and diff_j % 2 == 0:
print('Impossible')
return
moves = []
while diff_i < 0 and diff_i // -2 > diff_j:
if j == 0:
diff_i += 2
diff_j -= 1
i -= 2
j += 1
moves.append('UR')
continue
diff_i += 2
diff_j += 1
i -= 2
j -= 1
moves.append('UL')
while diff_i < 0:
diff_i += 2
diff_j -= 1
i -= 2
j += 1
moves.append('UR')
while diff_j > 0 and diff_j > diff_i // 2:
moves.append('R')
j += 2
diff_j -= 2
while diff_i > 0 and diff_i // -2 < diff_j:
if j == n - 1:
diff_i -= 2
diff_j += 1
i += 2
j -= 1
moves.append('LL')
continue
moves.append('LR')
diff_i -= 2
diff_j -= 1
i += 2
j += 1
while diff_i > 0:
diff_i -= 2
diff_j += 1
i += 2
j -= 1
moves.append('LL')
if diff_i == 0:
if diff_j > 0:
move = diff_j // 2
moves += ["R"] * move
else:
move = -diff_j // 2
moves += ["L"] * move
print(len(moves))
print(' '.join(moves))
if __name__ == "__main__":
n = int(input().strip())
i_start, j_start, i_end, j_end = input().strip().split(' ')
i_start, j_start, i_end, j_end = [int(i_start), int(j_start), int(i_end), int(j_end)]
printShortestPath(n, i_start, j_start, i_end, j_end)
Problem solution in Java.
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
static int INF=(int)1e9;
static String[] neighborS = {"UL", "UR", "R", "LR", "LL", "L"};
static int[] neighborI = {-2, -2, 0, 2, 2, 0};
static int[] neighborJ = {-1, 1, 2, 1, -1, -2};
static void printShortestPath(int n, int i_start, int j_start, int i_end, int j_end) {
// Print the distance along with the sequence of moves.
Pair[] q = new Pair[n*n];
int qt=0, qh=0;
q[qt++]=new Pair(i_start, j_start);
int[][] dist = new int[n][n];
Pair[][] prev = new Pair[n][n];
String[][] prevS = new String[n][n];
for(int i=0; i<n; ++i)
Arrays.fill(dist[i], INF);
dist[i_start][j_start]=0;
while(qt>qh) {
Pair p = q[qh++];
for(int i=0; i<6; ++i) {
int nI=p.a+neighborI[i], nJ=p.b+neighborJ[i];
if(nI<0||nI>=n||nJ<0||nJ>=n||dist[nI][nJ]<INF)
continue;
prevS[nI][nJ]=neighborS[i];
prev[nI][nJ] = new Pair(p.a, p.b);
dist[nI][nJ]=dist[p.a][p.b]+1;
q[qt++]=new Pair(nI, nJ);
}
}
if(dist[i_end][j_end]>=INF)
System.out.println("Impossible");
else {
String s="";
for(Pair p=new Pair(i_end, j_end); prev[p.a][p.b]!=null; p=prev[p.a][p.b])
s=prevS[p.a][p.b]+" "+s;
System.out.println(dist[i_end][j_end]+"\n"+s);
}
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int i_start = in.nextInt();
int j_start = in.nextInt();
int i_end = in.nextInt();
int j_end = in.nextInt();
printShortestPath(n, i_start, j_start, i_end, j_end);
in.close();
}
static class Pair {
int a, b;
Pair(int a, int b) {
this.a=a;
this.b=b;
}
}
}
Problem solution in C++.
#include <stdio.h>
#include <string.h>
#include <queue>
#include <stack>
#include <string>
using namespace std;
int dx[] = {-1, 1, 2, 1, -1, -2};
int dy[] = {-2, -2, 0, 2, 2, 0};
int from[210][210];
int N;
int yt, xt;
char moveNames[][5] = {"UL", "UR", "R", "LR", "LL", "L"};
queue<int> q;
stack<int> moves;
int main(){
memset(from, -1, sizeof(from));
int yf, xf;
scanf("%d", &N);
scanf("%d %d %d %d", &yf, &xf, &yt, &xt);
q.push(yf*1000 + xf);
from[yf][xf] = 10;
while(!q.empty()){
int now = q.front();
q.pop();
xf = now % 1000;
yf = now / 1000;
if(xf == xt && yf == yt) break;
for(int i=0; i<6; i++){
int nx = xf + dx[i];
int ny = yf + dy[i];
if(nx < 0) continue;
if(ny < 0) continue;
if(nx >= N) continue;
if(ny >= N) continue;
if(from[ny][nx] == -1){
from[ny][nx] = i;
q.push(ny*1000 + nx);
}
}
}
if(xf == xt && yf == yt){
while(from[yf][xf] != 10){
moves.push(from[yf][xf]);
int ny = yf - dy[from[yf][xf]];
int nx = xf - dx[from[yf][xf]];
yf = ny;
xf = nx;
}
printf("%d\n", moves.size());
while(!moves.empty()){
int mo = moves.top();
moves.pop();
printf("%s", moveNames[mo]);
if(moves.empty()) printf("\n");
else printf(" ");
}
}
else{
printf("Impossible\n");
}
return 0;
}
Problem solution in C.
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>
typedef struct s_action
{
int step;
int UL;
int UR;
int R;
int LR;
int LL;
int L;
} t_action;
void ft_impossible()
{
printf("Impossible");
exit(0);
}
void init_action(t_action *action)
{
action->step = 0;
action->UL = 0;
action->UR = 0;
action->R = 0;
action->LR = 0;
action->LL = 0;
action->L = 0;
}
void UL(int *i_start, int *j_start, t_action *action, int n)
{
*i_start -= 2;
*j_start -= 1;
if (*j_start < 0)
ft_impossible();
action->step += 1;
action->UL += 1;
}
void UR(int *i_start, int *j_start, t_action *action, int n)
{
*i_start -= 2;
*j_start += 1;
if (*j_start >= n)
ft_impossible();
action->step += 1;
action->UR += 1;
}
void R(int *j_start, t_action *action, int n)
{
*j_start += 2;
if (*j_start >= n)
ft_impossible();
action->step += 1;
action->R += 1;
}
void LR(int *i_start, int *j_start, t_action *action, int n)
{
*i_start += 2;
*j_start += 1;
if (*j_start >= n)
ft_impossible();
action->step += 1;
action->LR += 1;
}
void LL(int *i_start, int *j_start, t_action *action, int n)
{
*i_start += 2;
*j_start -= 1;
if (*j_start < 0)
ft_impossible();
action->step += 1;
action->LL += 1;
}
void L(int *j_start, t_action *action, int n)
{
*j_start -= 2;
if (*j_start < 0)
ft_impossible();
action->step += 1;
action->L += 1;
}
void print_action(t_action action)
{
printf("%d\n", action.step);
while (action.UL--)
printf("UL ");
while (action.UR--)
printf("UR ");
while (action.R--)
printf("R ");
while (action.LR--)
printf("LR ");
while (action.LL--)
printf("LL ");
while (action.L--)
printf("L ");
}
void printShortestPath(int n, int i_start, int j_start, int i_end, int j_end) {
// Print the distance along with the sequence of moves.
t_action action;
int vertical;
int down_move;
init_action(&action);
vertical = (i_end - i_start > 0) ? i_end - i_start : i_start - i_end;
if (vertical % 2 == 1)
ft_impossible();
while (i_end < i_start)
{
if (j_end <= j_start)
UL(&i_start, &j_start, &action, n);
else
UR(&i_start, &j_start, &action, n);
}
down_move = vertical / 2 - action.step;
while (j_end - down_move > j_start)
R(&j_start, &action, n);
while (i_end > i_start)
{
if (j_end >= j_start)
LR(&i_start, &j_start, &action, n);
else
LL(&i_start, &j_start, &action, n);
}
while (j_end < j_start)
L(&j_start, &action, n);
if (j_end != j_start)
ft_impossible();
print_action(action);
}
int main() {
int n;
scanf("%i", &n);
int i_start;
int j_start;
int i_end;
int j_end;
scanf("%i %i %i %i", &i_start, &j_start, &i_end, &j_end);
printShortestPath(n, i_start, j_start, i_end, j_end);
return 0;
}
0 Comments