In this HackerRank Castle on the Grid Interview preparation kit problem you have Given a grid, a start, and a goal, determine the minimum number of moves to get to the goal.
Problem solution in Python programming.
import numbers
import math
from collections import namedtuple,deque
class point(namedtuple("point", "i j")):
def __eq__(self,o):
return self.i == o.i and self.j == o.j
def __ne__(self, o):
return self.i != o.i or self.j != o.j
def __lt__(self, o):
return self.i < o.i or self.j < o.j
def __gt__(self, o):
return self.i > o.i or self.j > o.j
def __le__(self, o):
return self.i <= o.i or self.j <= o.j
def __ge__(self, o):
return self.i >= o.i or self.j >= o.j
def __rshift__(self,o):
return self.i >= o.i and self.j >= o.j
def __lshift__(self,o):
return self.i <= o.i and self.j <= o.j
def __hash__(self):
return hash((self.i, self.j))
def __repr__(self):
return 'p(%r, %r)' % self
def __add__(self,o):
if isinstance(o, point):
return point.__new__(point,self.i+o.i,self.j+o.j)
if isinstance(o, numbers.Number):
return point.__new__(point,self.i+o,self.j+o)
return NotImplemented
def __iadd__(self,o):
return self.__add__(o)
def __sub__(self,o):
if isinstance(o, point):
return point.__new__(point,self.i-o.i,self.j-o.j)
if isinstance(o, numbers.Number):
return point.__new__(point,self.i-o,self.j-o)
return NotImplemented
def inbound(self,a,b=None):
if b is None:
a,b = point(0,0),a
im,ix = sorted([a.i,b.i])
jm,jx = sorted([a.j,b.j])
return im <= self.i and self.i < ix and jm <= self.j and self.j < jx
def distance(self,o):
return abs(self.i-o.i)+abs(self.j-o.j)
#return math.sqrt((self.i-o.i)**2+(self.j-o.j)**2)
def __isub__(self,o):
return self.__sub__(o)
def __neg__(self):
return point.__new__(point,-self.i,-self.j)
def I():
return point.__new__(point,1,0)
def J():
return point.__new__(point,0,1)
class grid(list):
def __getitem__(self, *args, **kwargs):
if isinstance(args[0], point):
return self[args[0].i][args[0].j]
else:
return list.__getitem__(self, *args, **kwargs)
def __setitem__(self, *args, **kwargs):
if isinstance(args[0], point):
self[args[0].i][args[0].j] = args[1]
else:
return list.__setitem__(self, *args, **kwargs)
def __repr__(self):
return "\n".join(["".join(map(lambda x:str(x)[-1],a)) for a in self])
around = (-point.I(),-point.J(),point.J(),point.I())
n = int(input())
b = grid([list(input()) for _ in range(n)])
_ = list(map(int,input().split()))
p = point(_[0],_[1])
f = point(_[2],_[3])
b[p] = "#"
b[f] = "E"
q = deque([(p,0)])
vg = grid([[False for _ in range(len(b[0]))] for _ in range(len(b))])
while len(q):
c,d = q.popleft()
vg[c] = True
#print(c,b[c.i][c.j])
if c == f:
break
if b[c] == ".":
b[c] = "="
for di in around:
pt = c
while True:
pt += di
if pt.inbound(point(0,0) ,point(len(b),len(b[0]))) and (b[pt] == "." or b[pt] == "E") :
q.append((pt,d+1))
vg[pt] = True
if b[pt] == ".":
b[pt] = d+1
else:
break
#print(c,ar)
#print(q)
#print(b)
print(d)Problem solution in Java Programming.
import java.io.*;
import java.util.*;
public class Solution {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
scanner.useDelimiter("\n");
int n = scanner.nextInt();
char[][] grid = new char[n][n];
for (int i = 0; i < n; i++) {
String str = scanner.next();
grid[i] = str.toCharArray();
}
String coords = scanner.next();
String[] split = coords.split(" ");
XY start = new XY(Integer.parseInt(split[0]), Integer.parseInt(split[1]));
XY end = new XY(Integer.parseInt(split[2]), Integer.parseInt(split[3]));
Set<XY> visited = new HashSet<XY>();
System.out.println(minSteps(grid, start, end, visited));
}
private static int minSteps(char[][] grid, XY curr, XY end, Set<XY> visited) {
Queue<XY> queue = new LinkedList<XY>();
queue.add(curr);
visited.add(curr);
Queue<Integer> step = new LinkedList<Integer>();
step.add(0);
while (!queue.isEmpty()) {
XY nextXY = queue.remove();
int hop = step.remove();
if (nextXY.equals(end)) return hop;
List<XY> next = getNext(grid, nextXY, visited);
visited.addAll(next);
queue.addAll(next);
for (int i = 0; i < next.size(); i++) {
step.add(hop + 1);
}
}
return Integer.MAX_VALUE;
}
private static List<XY> getNext(char[][] grid, XY curr, Set<XY> visited) {
List<XY> next = new ArrayList<XY>();
if (curr.dir == null || curr.dir == Dir.Y) {
int x = curr.x;
for (int i = x - 1; i >= 0; i--) {
if (grid[i][curr.y] == 'X') break;
final XY xy = new XY(i, curr.y, Dir.X);
if (!visited.contains(xy)) next.add(xy);
}
for (int i = x + 1; i < grid.length; i++) {
if (grid[i][curr.y] == 'X') break;
final XY xy = new XY(i, curr.y, Dir.X);
if (!visited.contains(xy)) next.add(xy);
}
}
if (curr.dir == null || curr.dir == Dir.X) {
int y = curr.y;
for (int i = y - 1; i >= 0; i--) {
if (grid[curr.x][i] == 'X') break;
final XY xy = new XY(curr.x, i, Dir.Y);
if (!visited.contains(xy)) next.add(xy);
}
for (int i = y + 1; i < grid.length; i++) {
if (grid[curr.x][i] == 'X') break;
final XY xy = new XY(curr.x, i, Dir.Y);
if (!visited.contains(xy)) next.add(xy);
}
}
return next;
}
private static class XY {
int x, y;
Dir dir;
public XY(int x, int y) {
this.x = x;
this.y = y;
dir = null;
}
public XY(int x, int y, Dir dir) {
this.x = x;
this.y = y;
this.dir = dir;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
XY xy = (XY) o;
return x == xy.x && y == xy.y;
}
@Override
public int hashCode() {
return 31 * x + y;
}
@Override
public String toString() {
return "XY{" +
"x=" + x +
", y=" + y +
", dir=" + dir +
'}';
}
}
private enum Dir {
X, Y;
}
}Problem solution in C++ programming.
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <deque>
using namespace std;
// -1 for break; 0 for continue; 1 for OK
int func(vector<vector<char>>& vlist, deque<int>& pst, vector<vector<int>>& visited, int tx, int ty, int x1, int y1)
{
int n = vlist.size();
if(tx < 0 || tx >= n || ty < 0 || ty >= n)
return -1;
if(vlist[tx][ty] == 'X')
return -1;
if(visited[tx][ty] == 1)
return 0;
visited[tx][ty] = 1;
pst.push_back(tx + ty *n);
if(tx == x1 && ty == y1)
return 1;
return 0;
}
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int n;
cin >> n;
vector<vector<char>> vlist;
vector<vector<int>> vvst;
vlist.resize(n);
vvst.resize(n);
for(int i = 0; i < n; i ++)
{
for(int j =0; j < n; j ++)
{
char c;
cin >> c;
vlist[i].push_back(c);
vvst[i].push_back(0);
}
}
int x0, y0, x1, y1;
cin >> x0 >> y0 >> x1 >> y1;
deque<int> pst;
pst.push_back(x0 + n * y0);
int level = 0;
bool found = false;
deque<int> tempst;
while(true)
{
if(pst.empty())
{
pst = tempst;
tempst.clear();
}
if(pst.empty() || found)
break;
level ++;
while(!pst.empty())
{
if(found)
break;
int v = pst.front();
pst.pop_front();
int tx = v % n;
int ty = v / n;
for(int k = tx - 1; k >=0; k --)
{
int rn = func(vlist, tempst, vvst, k, ty, x1, y1);
if(rn == -1)
break;
else if(rn == 1)
{
found = true;
break;
}
}
for(int k = tx + 1; k < n; k ++)
{
int rn = func(vlist, tempst, vvst, k, ty, x1, y1);
if(rn == -1)
break;
else if(rn == 1)
{
found = true;
break;
}
}
for(int k = ty - 1; k >=0; k --)
{
int rn = func(vlist, tempst, vvst, tx, k, x1, y1);
if(rn == -1)
break;
else if(rn == 1)
{
found = true;
break;
}
}
for(int k = ty + 1; k < n; k ++)
{
int rn = func(vlist, tempst, vvst, tx, k, x1, y1);
if(rn == -1)
break;
else if(rn == 1)
{
found = true;
break;
}
}
}
}
cout << level << endl;
return 0;
}Problem solution in C programming.
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
typedef struct {
int x;
int y;
} Gridpoint;
int insertGrid(Gridpoint *queue, int x, int y, int wr_ptr) {
queue[wr_ptr].x = x;
queue[wr_ptr].y = y;
wr_ptr += 1;
return wr_ptr;
}
int MovePath(int **grid, int x, int y, int N, int wr_ptr, Gridpoint *queue) {
int step = grid[x][y] + 1;
//printf("(%d, %d). step = %d\n", x, y, step);
// move up
for (int i=x-1;i>=0;i--) {
if (grid[i][y] == -1) {
break;
}
if (grid[i][y] == 0) {
grid[i][y] = step;
wr_ptr = insertGrid(queue, i, y, wr_ptr);
}
}
// move down
for (int i=x+1;i<N;i++) {
if (grid[i][y] == -1) {
break;
}
if (grid[i][y] == 0) {
grid[i][y] = step;
wr_ptr = insertGrid(queue, i, y, wr_ptr);
}
}
// move right
for (int i=y+1;i<N;i++) {
if (grid[x][i] == -1) {
break;
}
if (grid[x][i] == 0) {
grid[x][i] = step;
wr_ptr = insertGrid(queue, x, i, wr_ptr);
}
}
// move left
for (int i=y-1;i>=0;i--) {
if (grid[x][i] == -1) {
break;
}
if (grid[x][i] == 0) {
grid[x][i] = step;
wr_ptr = insertGrid(queue, x, i, wr_ptr);
}
}
return wr_ptr;
}
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int N;
scanf("%d\n", &N);
int **grid = (int **)malloc(sizeof(int *)*N);
char tmp;
for (int i = 0;i<N;i++) {
grid[i] = (int *)malloc(sizeof(int)*N);
for (int j = 0;j<N;j++) {
scanf("%c\n", &tmp);
if (tmp == 'X') {
grid[i][j] = -1;
} else {
grid[i][j] = 0;
}
}
}
int cur_x, cur_y, end_x, end_y;
scanf("%d %d %d %d", &cur_x, &cur_y, &end_x, &end_y);
Gridpoint *queue = (Gridpoint *)malloc(sizeof(Gridpoint) *100);
int wr_ptr = 0;
int rd_ptr = 0;
//printf("(%d, %d) (%d, %d)\n", cur_x, cur_y, end_x, end_y);
// BFS iteratively on all nodes
while (rd_ptr <= wr_ptr) {
wr_ptr = MovePath(grid, cur_x, cur_y, N, wr_ptr, queue);
//printf("wr_ptr = %d\n", wr_ptr);
cur_x = queue[rd_ptr].x;
cur_y = queue[rd_ptr].y;
rd_ptr++;
//printf("(%d, %d). rd_ptr = %d\n", cur_x, cur_y, rd_ptr);
}
printf("%d", grid[end_x][end_y]);
return 0;
}Problem solution in 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', inputStdin => {
inputString += inputStdin;
});
process.stdin.on('end', function() {
inputString = inputString.replace(/\s*$/, '')
.split('\n')
.map(str => str.replace(/\s*$/, ''));
main();
});
function readLine() {
return inputString[currentLine++];
}
// Complete the minimumMoves function below.
function minimumMoves(grid, startRow, startCol, goalRow, goalCol) {
// initialize a 2d matrix to track visited nodes and its parents
const visited = Array(grid.length).fill(false).map(_ => Array(grid[0].length).fill(false).map(_ => ({visited: false, parent: null})));
visited[startRow][startCol].visited = true;
console.log(visited);
const rowQueue = [startRow];
const colQueue = [startCol];
let moves = 0;
let parent = null;
while (rowQueue.length !== 0) {
const row = rowQueue.shift();
const col = colQueue.shift();
if (row === goalRow && col === goalCol) {
parent = visited[row][col].parent;
break;
}
exploreNeighbours(row, col);
}
console.log(visited);
while (parent !== null) {
console.log(parent);
moves++;
parent = visited[parent[0]][parent[1]].parent;
}
return moves;
function exploreNeighbours(row, col) {
// north, south, east, west directon vectors
const dc = [0, 0, -1, +1];
const dr = [-1, +1, 0, 0];
for (let i = 0; i < 4; i++) {
let cc = col;
let rr = row;
while (true) {
cc += dc[i];
rr += dr[i];
// stop at out of bounds
if (cc < 0 || rr < 0) break;
if (rr > grid.length - 1 || cc > grid[0].length - 1) break;
// stop visited or blocked cells
if (visited[rr][cc].visited) continue;
if (grid[rr][cc] === 'X') break;
colQueue.push(cc);
rowQueue.push(rr);
visited[rr][cc].visited = true;
visited[rr][cc].parent = [row, col];
}
}
}
}
function main() {
const ws = fs.createWriteStream(process.env.OUTPUT_PATH);
const n = parseInt(readLine(), 10);
let grid = [];
for (let i = 0; i < n; i++) {
const gridItem = readLine();
grid.push(gridItem);
}
const startXStartY = readLine().split(' ');
const startX = parseInt(startXStartY[0], 10);
const startY = parseInt(startXStartY[1], 10);
const goalX = parseInt(startXStartY[2], 10);
const goalY = parseInt(startXStartY[3], 10);
const result = minimumMoves(grid, startX, startY, goalX, goalY);
ws.write(result + '\n');
ws.end();
}
0 Comments