Algorithm

Problem Name: Data Structures - Castle on the Grid

Problem Link: https://www.hackerrank.com/challenges/castle-on-the-grid/problem?isFullScreen=true

In this HackerRank in Data Structures - Castle on the Grid solutions

You are given a square grid with some cells open (.) and some blocked (X). Your playing piece can move along any row or column until it reaches the edge of the grid or a blocked cell. Given a grid, a start and a goal, determine the minmum number of moves to get to the goal.

 

Example.

gird = ['...' , '.X.' , '...', '...']

startX = 0

startY = 0

goalX = 1

goalY = 2

The grid is shown below:

 

...
.X.
...

The starting position (startX,startY) = (0,0) o start in the top left corner. The goal is (goalX, goalY) = (1,2). The path is (0,0) -> (0,2) -> (1,2) It takes 2 moves to reach the goal.

Function Description
Complete the minimumMoves function in the editor.

 

minimumMoves has the following parameter(s):

 

  • string grid[n]: an array of strings that represent the rows of the grid
  • int startX: starting X coordinate
  • int startY: starting Y coordinate
  • int goalX: ending X coordinate
  • int goalY: ending Y coordinate

 

Returns

 

  • int: the minimum moves to reach the goal

Input Format

The first line contains an integer n the size of the array grid.
Each of the next n lines contains a string of length n,

The last line contains four space-separated integers,

startX,startY,goalX,goalY

Constraints

  • 1 <= n <= 100
  • 0 <= startX,startY,goalX,goalY < n

Sample Input

STDIN       FUNCTION
-----       --------
3           grid[] size n = 3
.X.         grid = ['.X.','.X.', '...']
.X.
...
0 0 0 2     startX = 0, startY = 0, goalX = 0, goalY = 2

Sample Output

3

Explanation

Here is a path that one could follow in order to reach the destination in 3 steps:

 

 (0,0) -> (2,0) -> (2,2) -> (0,2)

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming


#include <bits/stdc++.h>

using namespace std;

string ltrim(const string &);
string rtrim(const string &);
vector < string> split(const string &);

/*
 * Complete the 'minimumMoves' function below.
 *
 * The function is expected to return an INTEGER.
 * The function accepts following parameters:
 *  1. STRING_ARRAY grid
 *  2. INTEGER startX
 *  3. INTEGER startY
 *  4. INTEGER goalX
 *  5. INTEGER goalY
 */

int minimumMoves(vector<string> grid, int startX, int startY, int goalX, int goalY) {

  int col = grid[0].size();
  int row = grid.size();
  
  int track[row][col];
  pair < int, int> predecessor[row][col]; 
  
  for(int i = 0; i  <  row; i++) {
      for(int j = 0; j  <  col; j++) {
          if(grid[i][j] == 'X') {
              track[i][j] = 3;
              continue;
          }
          
          track[i][j] = 1;
      }
  }
  
  queue<pair < int, int>> q;
  
  q.push(make_pair(startX, startY));
  track[startX][startY]++;
  
  while(!q.empty()> {
     pair < int, int> coord = q.front();
     q.pop();
     
          for(int i = coord.second - 1; i >= 0; i--) {
         if(track[coord.first][i] == 1) {
             q.push(make_pair(coord.first, i));
             predecessor[coord.first][i] = coord;
             track[coord.first][i]++;
         } else {
             break;
         } 
     }

     
     for(int i = coord.first - 1; i >= 0; i--) {
         if(track[i][coord.second] == 1) {
             q.push(make_pair(i, coord.second));
             predecessor[i][coord.second] = coord;
             track[i][coord.second]++;
         } else {
             break;
         } 
     }
     
     for(int i = coord.second + 1; i < col; i++) {
         if(track[coord.first][i] == 1) {
             q.push(make_pair(coord.first, i));
             predecessor[coord.first][i] = coord;
             track[coord.first][i]++;
         } else {
             break;
         } 
     }
     
     for(int i = coord.first + 1; i  <  row; i++) {
         if(track[i][coord.second] == 1) {
             q.push(make_pair(i, coord.second));
             predecessor[i][coord.second] = coord;
             track[i][coord.second]++;
         } else {
             break;
         } 
     }    
     
     if(predecessor[goalX][goalY].first != 0 && predecessor[goalX][goalY].second != 0) {
         break;
     }
  }

  stack < pair<int, int>> container;
  container.push(make_pair(goalX, goalY)>;
  
  pair < int, int> temp = predecessor[goalX][goalY];
  while (true) {
      if(temp.first == startX && temp.second == startY) {
          container.push(temp);
          break;
      } else {
          container.push(temp);
          temp = predecessor[temp.first][temp.second];
      }
  }
  
  return container.size() - 1;
}

int main()
{
    ofstream fout(getenv("OUTPUT_PATH"));

    string n_temp;
    getline(cin, n_temp);

    int n = stoi(ltrim(rtrim(n_temp)));

    vector < string> grid(n);

    for (int i = 0; i  <  n; i++) {
        string grid_item;
        getline(cin, grid_item);

        grid[i] = grid_item;
    }

    string first_multiple_input_temp;
    getline(cin, first_multiple_input_temp);

    vector < string> first_multiple_input = split(rtrim(first_multiple_input_temp));

    int startX = stoi(first_multiple_input[0]);

    int startY = stoi(first_multiple_input[1]);

    int goalX = stoi(first_multiple_input[2]);

    int goalY = stoi(first_multiple_input[3]);

    int result = minimumMoves(grid, startX, startY, goalX, goalY);

    fout << result << "\n";

    fout.close();

    return 0;
}

string ltrim(const string &str) {
    string s(str);

    s.erase(
        s.begin(),
        find_if(s.begin(), s.end(), not1(ptr_fun < int, int>(isspace)))
    );

    return s;
}

string rtrim(const string &str) {
    string s(str);

    s.erase(
        find_if(s.rbegin(), s.rend(), not1(ptr_fun < int, int>(isspace))).base(),
        s.end()
    );

    return s;
}

vector < string> split(const string &str) {
    vector<string> tokens;

    string::size_type start = 0;
    string::size_type end = 0;

    while ((end = str.find(" ", start)) != string::npos) {
        tokens.push_back(str.substr(start, end - start));

        start = end + 1;
    }

    tokens.push_back(str.substr(start));

    return tokens;
}
Copy The Code & Try With Live Editor

#2 Code Example with Javascript Programming

Code - Javascript Programming


'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', function(inputStdin) {
    inputString += inputStdin;
});

process.stdin.on('end', function() {
    inputString = inputString.split('\n');

    main();
});

function readLine() {
    return inputString[currentLine++];
}

/*
 * Complete the 'minimumMoves' function below.
 *
 * The function is expected to return an INTEGER.
 * The function accepts following parameters:
 *  1. STRING_ARRAY grid
 *  2. INTEGER startX
 *  3. INTEGER startY
 *  4. INTEGER goalX
 *  5. INTEGER goalY
 */

function minimumMoves(grid, startX, startY, goalX, goalY) {
  const start = `${startX},${startY}`;
  const goal = `${goalX},${goalY}`;
  const len = grid.length;
  const queue = [start];
  const adjacencyList = new Map([[start, []]]);

  const addNode = (origin) => {
    adjacencyList.set(origin, []);
  }

  const addEdge = (origin, destination) => {
    if (!adjacencyList.get(destination)) {
      addNode(destination);
      queue.push(destination);
    }
    adjacencyList.get(origin).push(destination);
  }

  const bfs = (start, goal) => {
    const visited = new Set(start);
    const queue = [start];
    const predecessors = {};

    while (queue.length > 0) {
      const node = queue.shift();

      if (node === goal) {
        const path = [goal];
        let pre = predecessors[goal];

        while (pre !== start) {
          path.push(pre);
          pre = predecessors[pre];
        }
        
        return path.length;
      }

      const neighborNodes = adjacencyList.get(node);
      for (let i=0; i < neighborNodes.length; i++) {
        const neighborNode = neighborNodes[i];
        if (!visited.has(neighborNode)) {
          queue.push(neighborNode);
          visited.add(neighborNode);
          predecessors[neighborNode] = node;
        }
      }
    }
  }

  while (queue.length > 0) {
    const step = queue.shift();
    const [x, y] = step.split(',').map(v => parseInt(v, 0));
    
    if (x > 0) { // up
      for (let i=x-1; i>=0; i--) {
        if (grid[i][y] === 'X') break;
        addEdge(step, `${i},${y}`);
      }
    }
    if (x  <  len-1) { // down
      for (let i = x + 1; i < len; i++) {
        if (grid[i][y] === 'X') break;
        addEdge(step, `${i},${y}`);
      }
    }
    if (y > 0) { // left
      for (let i = y-1; i >= 0; i--) {
        if (grid[x][i] === 'X') break;
        addEdge(step, `${x},${i}`);
      }
    }
    if (y  <  len-1) { // right
      for (let i = y+1; i < len; i++) {
        if (grid[x][i] === 'X') break;
        addEdge(step, `${x},${i}`);
      }
    }
  }
  
  return bfs(start, goal)
}

function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const n = parseInt(readLine().trim(), 10);

    let grid = [];

    for (let i = 0; i  <  n; i++) {
        const gridItem = readLine();
        grid.push(gridItem);
    }

    const firstMultipleInput = readLine().replace(/\s+$/g, '').split(' ');

    const startX = parseInt(firstMultipleInput[0], 10);

    const startY = parseInt(firstMultipleInput[1], 10);

    const goalX = parseInt(firstMultipleInput[2], 10);

    const goalY = parseInt(firstMultipleInput[3], 10);

    const result = minimumMoves(grid, startX, startY, goalX, goalY);

    ws.write(result + '\n');

    ws.end();
}
Copy The Code & Try With Live Editor

#4 Code Example with Java Programming

Code - Java Programming


import java.util.*;

public class Solution {

    static int[] xMove = {-1, 0, 1, 0 };
    static int[] yMove = { 0, 1, 0, -1};

    public static boolean isSafe (int n, int x, int y, char[][] matrix) {
        return (x >= 0 && y >= 0 && x  <  n && y < n && matrix[x][y] == '.');
    }

    public static int solve(int n, char[][] matrix, int startX, int startY, int goalX, int goalY) {
        LinkedList queueX = new LinkedList<>();
        LinkedList < Integer> queueY = new LinkedList<>();
        int[][] step = new int[n+1][n+1];
        boolean[][] visited = new boolean[n+1][n+1];
        queueX.add(startX);
        queueY.add(startY);
        visited[startX][startY] = true;
        while (!queueX.isEmpty()) {
            int curX = queueX.poll();
            int curY = queueY.poll();
            for (int i = 0; i  <  4; i++) {
                int index = 1;
                while (isSafe(n, curX+xMove[i]*index, curY + yMove[i]*index, matrix)
                        && !visited[curX+xMove[i]*index][curY + yMove[i]*index]) {
                    int nextX = curX + xMove[i]*index;
                    int nextY = curY + yMove[i]*index;
                    visited[nextX][nextY] = true;
                    queueX.add(nextX);
                    queueY.add(nextY);
                    step[nextX][nextY] = step[curX][curY] +1;
                    if (nextX == goalX && nextY == goalY) {
                        return step[nextX][nextY];
                    }
                    index++;
                }

            }
        }
        return -1;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        char[][] matrix = new char[n + 1][n + 1];
        scanner.nextLine();
        for (int i = 0; i  <  n; i++) {
            String line = scanner.nextLine();
            for (int j = 0; j  <  n; j++) {
                matrix[i][j] = line.charAt(j);
            }
        }
        int startX = scanner.nextInt();
        int startY = scanner.nextInt();
        int goalX = scanner.nextInt();
        int goalY = scanner.nextInt();
        int result = solve(n, matrix, startX, startY, goalX, goalY);
        System.out.println(result);
        scanner.close();

    }
}
Copy The Code & Try With Live Editor

#3 Code Example with Python Programming

Code - Python Programming


#!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'minimumMoves' function below.
#
# The function is expected to return an INTEGER.
# The function accepts following parameters:
#  1. STRING_ARRAY grid
#  2. INTEGER startX
#  3. INTEGER startY
#  4. INTEGER goalX
#  5. INTEGER goalY
#
from collections import deque


def minimumMoves(grid, startX, startY, goalX, goalY):
    visited = set()
    queue = deque([[startX, startY, 0]])

    while queue:
        x, y, moves_qty = queue.popleft()
        moves_qty += 1

        for edge_x, edge_y in get_edges(x, y):
            if (edge_x, edge_y) in visited:
                continue
            if goalX == edge_x and goalY == edge_y:
                return moves_qty

            visited.add((edge_x, edge_y))
            queue.append([edge_x, edge_y, moves_qty])
    
    return -1

def get_edges(x, y):
    """
    The hack is here. In a regular BFS algorithm we would only look for the neighbours.
    As we can move multiple cells in the same column or row with only one movement, we need
    to consider that extra movements, which is doing on the while statement.
    """
    moves = (
        (0, -1),
        (0, 1),
        (-1, 0),
        (1, 0),
    )
    edges = []
    for move_x, move_y in moves:
        canMove = True
        edge_x, edge_y = x, y
        while canMove:

            edge_x, edge_y = edge_x + move_x, edge_y + move_y
            try:
                if grid[edge_x][edge_y] == '.':
                    edges.append((edge_x, edge_y))
                else:
                    canMove = False
            except IndexError:
                canMove = False
    
    return edges

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    n = int(input().strip())

    grid = []

    for _ in range(n):
        grid_item = input()
        grid.append(grid_item)

    first_multiple_input = input().rstrip().split()

    startX = int(first_multiple_input[0])

    startY = int(first_multiple_input[1])

    goalX = int(first_multiple_input[2])

    goalY = int(first_multiple_input[3])

    result = minimumMoves(grid, startX, startY, goalX, goalY)

    fptr.write(str(result) + '\n')

    fptr.close()
Copy The Code & Try With Live Editor
Advertisements

Demonstration

Previous
[Solved] Balanced Brackets solution in Hackerrank - Hacerrank solution C, C++, java,js, Python
Next
[Solved] Down to Zero II solution in Hackerrank - Hacerrank solution C, C++, java,js, Python