In this HackerRank Snakes and Ladders: The Quickest Way Up problem solution Markov takes out his Snakes and Ladders game, stares at the board, and wonders: “If I can always roll the die to whatever number I want, what would be the least number of rolls to reach the destination?”
Problem solution in Python.
test_cases = int(input().strip())
for test_case in range(test_cases):
snake_count = int(input().strip())
shortcuts = {}
for snake in range(snake_count):
src, dst = [int(item)-1 for item in input().strip().split()]
shortcuts[src] = dst
ladder_count = int(input().strip())
for ladder in range(ladder_count):
src, dst = [int(item)-1 for item in input().strip().split()]
shortcuts[src] = dst
board = [0] + [None] * 99
dst = 0
while dst < 99:
dst += 1
moves = board[dst]
sources = [cell for cell in board[max(dst-6, 0):dst] if cell is not None]
if not sources:
continue
moves = min(sources) + 1
new_dst = shortcuts.get(dst, dst)
if board[new_dst] is None or moves < board[new_dst]:
board[new_dst] = moves
dst = min(dst, new_dst)
print(board[-1] if board[-1] is not None else '-1')
Problem solution in Java.
import java.io.*;
import java.util.*;
public class Solution {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
int M,N;
for (int i = 0; i < T; i++){
N = sc.nextInt();
HashMap<Integer,Integer> ladders = new HashMap<>();
int start, end;
for (int j = 0; j < N; j++){
start = sc.nextInt();
end = sc.nextInt();
ladders.put(start,end);
}
HashMap<Integer,Integer> snakes = new HashMap<>();
M = sc.nextInt();
for (int j = 0; j < M; j++){
start = sc.nextInt();
end = sc.nextInt();
snakes.put(start, end);
}
int[] distances = new int[100];
for (int j = 0; j < 100; j++){
distances[j] = Integer.MAX_VALUE;
}
getShortestPathToEnd(getGameGraph(ladders, snakes), 1, distances, 0);
System.out.println(distances[99] == Integer.MAX_VALUE ? -1 : distances[99]);
}
}
private static int getShortestPathToEnd(HashMap<Integer,HashSet<Integer>> graph, int start, int[] distances, int depth){
if (distances[start-1] > depth){
distances[start-1] = depth;
}
else{
return 0;
}
if (!graph.get(start).isEmpty()){
for (Integer child : graph.get(start)){
//System.out.println(start + " - " + child);
getShortestPathToEnd(graph, child, distances, depth + 1);
}
return 0;
}
else{
return -1;
}
}
private static HashMap<Integer,HashSet<Integer>> getGameGraph(HashMap<Integer,Integer> ladders, HashMap<Integer,Integer> snakes){
HashMap<Integer, HashSet<Integer>> graph = new HashMap<>();
HashSet<Integer> neighbours;
for (int i = 1; i <= 100; i++){
neighbours = new HashSet<Integer>();
for (int j = 1; j <= 6 && (i + j <= 100); j++){
if(ladders.containsKey(i+j)){
neighbours.add(ladders.get(i+j));
}
else if (snakes.containsKey(i+j)){
neighbours.add(snakes.get(i+j));
}
else{
neighbours.add(i+j);
}
}
graph.put(i, neighbours);
}
return graph;
}
}
Problem solution in C++.
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <queue>
using namespace std;
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int testNum;
int distanceArray[110][110];
cin>>testNum;
for(int i = 0; i < testNum; ++i){
memset(distanceArray, -1, sizeof(distanceArray));
//construct the board
int ladder, snake;
scanf("%d,%d", &ladder, &snake);
int start, end;
for(int j = 0; j < ladder; ++j){
scanf("%d,%d", &start, &end);
distanceArray[start][end] = 0;
}
for(int j = 0; j < snake; ++j){
scanf("%d,%d", &start, &end);
distanceArray[start][end] = 0;
}
for(int p = 1; p <= 100; ++p){
for(int q = 1; q <= 100; ++q){
for(int k = 1; k <= 100; ++k){
if(distanceArray[p][k] == -1 && k > p){
distanceArray[p][k] = (k - p - 1) / 6 + 1;
}
if(distanceArray[k][q] == -1 && q > k){
distanceArray[k][q] = (q - k - 1) / 6 + 1;
}
if(distanceArray[p][k] >= 0 && distanceArray[k][q] >= 0){
if(distanceArray[p][q] == -1 || distanceArray[p][q] > distanceArray[p][k] + distanceArray[k][q] ){
distanceArray[p][q] = distanceArray[p][k] + distanceArray[k][q];
}
}
}
}
}
cout<<distanceArray[1][100]<<endl;
}
return 0;
}
Problem solution in C.
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
struct Cell
{
int cost;
int visited;
int moves[6];
};
void Init(struct Cell *cells, int num)
{
for (int i = 0; i < num; i++)
{
for (int j = 1; j <= 6; j++)
{
int move = i + j;
cells[i].moves[j - 1] = (move >= 100) ? -1 : move;
}
cells[i].visited = 0;
cells[i].cost = -1;
}
cells[0].cost = 0;
}
void AddJump(struct Cell *cells, int from, int to)
{
int start = from - 6;
for (int i = start; i < from; i++)
{
if (i >= 0)
{
cells[i].moves[from - i - 1] = to;
//printf("From %d with roll %d jump to %dn", i, from - i, to);
}
}
}
int FindNext(struct Cell *cells, int num)
{
int next = -1, cost = -1;
for (int i = 0; i < num; i++)
{
if ((cells[i].visited == 0) &&
(cells[i].cost >= 0) &&
(cost == -1 || cells[i].cost < cost))
{
cost = cells[i].cost;
next = i;
}
}
return next;
}
int Trace(struct Cell *cells, int num)
{
int current = -1;
while ((current = FindNext(cells, num)) != -1)
{
for (int j = 0; j < 6; j++)
{
int n = cells[current].moves[j];
if (n >= 0 && cells[n].visited == 0)
{
int cost = cells[current].cost + 1;
if (cells[n].cost == -1 || cost < cells[n].cost)
{
cells[n].cost = cost;
}
}
}
cells[current].visited = 1;
}
return cells[num - 1].cost;
}
int main()
{
int total = 0;
struct Cell cells[100];
scanf("%d", &total);
for (int i = 0; i < total; i++)
{
int jumps = 0;
Init(cells, 100);
scanf("%d", &jumps);
for (int j = 0; j < jumps; j++)
{
int from, to;
scanf("%d %d", &from, &to);
AddJump(cells, from - 1, to - 1);
}
scanf("%d", &jumps);
for (int j = 0; j < jumps; j++)
{
int from, to;
scanf("%d %d", &from, &to);
AddJump(cells, from - 1, to - 1);
}
printf("%dn", Trace(cells, 100));
}
return 0;
}
