Castle on the grid hackerrank solution
You are given a grid with both sides equal to N/N. Rows and columns are numbered from 0/0 to N−1/N−1. There is a castle on the intersection of the aath row and the bbth column. Show Your task is to calculate the minimum number of steps it would take to move the castle from its initial position to the goal position (c/d). It is guaranteed that it is possible to reach the goal position from the initial position. LinkCastle on the Grid Complexity:time complexity is O(N^2) or O(N^3) space complexity is O(N^2) Execution:This solution works with the task as a 2D array. There are options available where you treat the task as a graph problem. In both cases each node it visited exactly once using BFS. On each node, I generate all nodes that are connected to this node in a straight line that is not broken by a ‘X’. I keep the distance data (integer) in the array itself. I store the nodes that have to be visited in a FIFO queue. Once the top element in the queue is the end, I terminate the algorithm. The data stored in the array are these:
Solution:from collections import deque class Point: def __init__(self, x, y): self.x = x self.y = y def __str__(self): return "X=%d,Y=%d" % (self.x, self.y) def getPointsFromPoint(N, arr, point): x = point.x y = point.y points = [] while x > 0: x -= 1 if arr[x][y] == 'X': break points.append(Point(x,y)) x = point.x while x < N-1: x += 1 if arr[x][y] == 'X': break points.append(Point(x,y)) x = point.x while y > 0: y -= 1 if arr[x][y] == 'X': break points.append(Point(x,y)) y = point.y while y < N-1: y += 1 if arr[x][y] == 'X': break points.append(Point(x,y)) return points def solveCastleGrid(N, arr, start, end): q = deque([start]) arr[start.x][start.y] = 0 while q: current_point = q.pop() current_distance = arr[current_point.x][current_point.y] points = getPointsFromPoint(N, arr, current_point) for p in points: if arr[p.x][p.y] == '.': arr[p.x][p.y] = current_distance + 1 q.appendleft(p) if p.x == end.x and p.y == end.y: return current_distance + 1 return -1 if __name__ == '__main__': N = input() arr = [0] * N for i in xrange(N): arr[i] = list(raw_input()) start_x, start_y, end_x, end_y = map(int, raw_input().split()) print solveCastleGrid(N, arr, Point(start_x, start_y), Point(end_x, end_y)) If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.
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])); SetProblem solution in C++ programming.#includeProblem solution in C programming.#include |