## Algorithm

Problem Name: Data Structures - Castle on the Grid

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));

}

``````
Copy The Code &

### #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();
});

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) => {
}

const addEdge = (origin, destination) => {
queue.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;
}

for (let i=0; i < neighborNodes.length; i++) {
const neighborNode = neighborNodes[i];
if (!visited.has(neighborNode)) {
queue.push(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;
}
}
if (x  <  len-1) { // down
for (let i = x + 1; i < len; i++) {
if (grid[i][y] === 'X') break;
}
}
if (y > 0) { // left
for (let i = y-1; i >= 0; i--) {
if (grid[x][i] === 'X') break;
}
}
if (y  <  len-1) { // right
for (let i = y+1; i < len; i++) {
if (grid[x][i] === 'X') break;
}
}
}

return bfs(start, goal)
}

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

let grid = [];

for (let i = 0; i  <  n; i++) {
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 &

### #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) {
int[][] step = new int[n+1][n+1];
boolean[][] visited = new boolean[n+1][n+1];
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;
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 &

### #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

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 &