# Castle on the Grid

# Castle on the Grid

codeharrier + 4 comments Hard to believe this was only 30 points.

HemanthKumar + 0 comments agree

michaelknight492 + 2 comments Is this problem suitable for a beginner. i.e. <3 months of programming experience?

abhi04_sati + 0 comments If you've started learning graphs then yes else no

lwchkg + 0 comments Yes unless your mindset is limited to "stacks and queues" only. Even though it needs a graph, the concepts are easy to figure out if you try the algorithm by hand.

vibhav_511 + 0 comments Agree..I have not have much knowledge in graphs so it is futile to waste time in this question

eduasinco + 1 comment This is as short as I could get and yes, I think I think the original problem was easier and then it was updated to something more complicated but with the same score.

def minimumMoves(grid, startY, startX, goalY, goalX): q = deque() q.append((startX, startY, 0, -1)) visited = {(startY, startX): 0} x, y = [-1, 0, 0, 1, 1], [0, 1, -1, 0, 1] def is_valid(x, y, new_dist): return x < len(grid) and y < len(grid) and x >= 0 and y >= 0 and grid[y][x] == '.' and ((y, x) not in visited or ((y, x) in visited and new_dist <= visited[(y, x)])) while q: n = q.pop() for k in range(4): dist = 0 if (x[k], y[k]) == (x[n[3]], y[n[3]]) else 1 if is_valid(n[0] + x[k], n[1] + y[k], n[2] + dist): visited[(n[1] + y[k], n[0] + x[k])] = n[2] + dist q.appendleft((n[0] + x[k], n[1] + y[k], n[2] + dist, k)) return visited[(goalY ,goalX)]

shgpt14 + 0 comments why we are appending on left of queue?? can somebody explain??

ianbibby + 4 comments This took longer to figure out than I would have liked, as I was also getting a mix of passes & failures for the test cases. It didn't help in the comments where people were simply saying a "simple BFS" is all that's needed.

So here's my attempt at consolidating some hints from others and myself.

Pay great attention to the note:

Note: You can move the castle from cell (a,b) to any (x,y) in a single step if there is a straight line between (a,b) and (x,y) that does not contain any forbidden cell. Here, "X" denotes a forbidden cell.

Since the problem is asking for the shortest number of

*turns*rather than*steps*, we modify a classic BFS accordingly.When getting a list of neighbors for a cell, rather than getting only the immediate surrounding neighbors, you can get all neighbors in the northern path (until either the top of the grid is reached, or a forbidden cell is encountered) and they would all have a distance of the current cells distance + 1. Repeat for east, south and west.

Once this is done, you'll observe that the target cell has a number relating to the minimum number of turns.

bgreenfield + 0 comments for a castle or rook, squares in a line are all immediate neigbors. its just a normal BFS, the expand step goes to up to 198 squares rather then 4 if you were only moving one square a step. if it helps forget the grid all together and think of each node as having N * 2 - 1 (one for each point on the same row or col) roads of length 1. at least it would be without blockages. finding neigbors you can reach in one move is a linear scan for each BFS step. in theory O(n^3) worst case. as you do one scan per square potentially.

ShubhamV06 + 0 comments Thank you very much! :D

virajparmar98 + 0 comments Thanx bro. Great help!

kamanashisroy + 0 comments The difference between the

`BFS`

(breadth-first search) and`Dijstra-shortest path`

algorithm is the relaxation.The pawn-move distance is monotonic function and hence it is suitable to use BFS. But the queen-move distance is non-monotonic function when a node is just explored, thus it requires relaxation . Dijkstra's shortest path algorithm is more suitable in this case. In our case we are doing rook move, for which Dijkstra is suitable as well.

The BFS ends when we explore the goal node. The Dijkstra's shortest path algorithm ends when we

`pop()`

goal node from the queue.Finally I did it with bidirectional-Dijkstra . I am not sure if it is faster than normal Dijkstra though. I guess in cases bidirectional-Dijkstra algorithm may expand more nodes than normal Dijkstra algorithm.

mcr431 + 2 comments Test case 12:

3

. . .

. X .

. X .

2 0 0 2

How does this equal 3???

StanislavLev + 1 comment Got the same problem, and it seems the question was updated recently. I had to fix main function, otherwise got "Out of bounds exception" in "for... String gridItem = gridItems[i];" statement. I suggested edits, will see their answer :).

priyam304 + 2 comments I am also getting the same problem. Even after I edited the main function I the output remains empty. I munaully printed the result variable but it shows in debug answer. which is correct answers(FYI) but I can't uses test cases now. Can you please share your main function.

rocknes + 0 comments You need to print the result in the BufferedWriter stream and not System.out.

StanislavLev + 0 comments I just took someone's from this discussion forum :) :

public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); String[] grid = new String[n];

`for(int grid_i = 0; grid_i < n; grid_i++){ grid[grid_i] = in.next(); } int startX = in.nextInt(); int startY = in.nextInt(); int goalX = in.nextInt(); int goalY = in.nextInt(); int result = minimumMoves(grid, startX, startY, goalX, goalY); System.out.println(result); in.close(); }`

jwpierceHackerRank Admin + 0 comments You are right, thanks. Output updated to reflect (2,0) -> (0,0) -> (0,2) in 2 moves.

love1024 + 5 comments Getting output 14 instead of 13 in test case 3.Anyone had the same output?

ejan16 + 1 comment Not sure how you implement your solution ... maybe you calculate shortest distances.. not shortest turns.

check this link.. He (knock_out) mentioned how shortest turn can be implmented by BSF ..

https://www.hackerrank.com/challenges/castle-on-the-grid/forum/comments/107995

ch1828 + 1 comment I have same issue. all other tests pass except this one. what's the maketake you made?

linpf + 1 comment Have the same issue here. still can not figure this out.

RobertsN + 4 comments Ensure you DON'T break the search (up,down,left,right) when hitting an already visited cell. There may be more cells beyond not yet visited. My condition is to stop when I hit "X" or the edge of the board. I originally made the same mistake :)

linpf + 0 comments [deleted]auld_brian + 0 comments Doh!! Thanks for sharing!! I got 14 instead of 13 on test case 2. That's gotta be it.

codemyassoff + 1 comment @RobertsN - If you hit an already visited cell and the number of turns it took you to visit that cell are less than the minimum number it took you to visit it so far, only then would you go ahead and revisit it. Am I right about that ?

RobertsN + 0 comments I actually don't have to cater for that since I used BFS rather than DFS (it is a queue challenge...) so any cell already visited will have it's lowest possible value. In other words if I previously visited a cell it's because it's already nearer via it's previous route than it can possibly be now.

I personally set the distance to numeric_limits::max() for all cells. Any cell with a different value has been visited.

giridarantce + 0 comments yes same for me

TSusanoPinto + 0 comments I failed test case #3. Went to check it, and it says the expected output is 16. My output is 13.

For what I understand you guys are saying that the correct output is 13 (the same as my solution's ouput), but for some reason it says it's expecting an output of 16... I'm confused!

Test case #3 is a 100-size maze with starting point 27 96, and ending point 94 33

_YASH_ + 1 comment They should mention that they aren't considering diagonal path as a straight line.

grinya_guitar + 1 comment I believe the

*castle*being a chess piece which is allowed to move either horizontal or vertical. But the dynamic grid doesn't recall a chessboard on the other hand =) the better proposition here is to state that the grid is always 8x8 and to amend addressing of the cells to fit chess alphanumeric manner.

amanul_002 + 1 comment My simple Java Solution - Just fill all the positions in the grid with the number of moves it takes to rech there. Populate the whole grid and then index to the (goalX, goalY) to find the answer. I have used Queue to store the next move. Also used a helper grip (of same dimension as nxn) to store 1 if that node has been visited, else one.

import java.io.

*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; import java.lang.*;public class Solution {

`static int game[][], helper[][]; static Queue <Point> move = new LinkedList<Point>(); static int n; static int minimumMoves(String[] grid, int startX, int startY, int goalX, int goalY) { n = grid.length; game = new int[n][n]; helper = new int[n][n]; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(grid[i].charAt(j) == '.') game[i][j] = 100; else game[i][j] = -1; } } Point start = new Point(startX, startY); move.add(start); game[startX][startY] = 0; while(!move.isEmpty()){ Point current = move.remove(); if(helper[current.x][current.y] == 0){ helper[current.x][current.y] = 1; moveGenerator(current); } } return game[goalX][goalY]; } public static void moveGenerator(Point p){ int x = p.x; int y = p.y; int value = game[x][y]; for(int i=x; i<n && game[i][y]!=-1;i++){ addStep(i,y,value); move.add(new Point(i,y)); } for(int i=x; i>=0 && game[i][y]!=-1;i--){ addStep(i,y,value); move.add(new Point(i,y)); } for(int i=y; i<n && game[x][i]!=-1;i++){ addStep(x,i,value); move.add(new Point(x,i)); } for(int i=y; i>=0 && game[x][i]!=-1;i--){ addStep(x,i,value); move.add(new Point(x,i)); } } public static void addStep(int x, int y, int value){ if(game[x][y] > value+1) game[x][y] = value+1; } public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); String[] grid = new String[n]; for(int grid_i = 0; grid_i < n; grid_i++){ grid[grid_i] = in.next(); } int startX = in.nextInt(); int startY = in.nextInt(); int goalX = in.nextInt(); int goalY = in.nextInt(); int result = minimumMoves(grid, startX, startY, goalX, goalY); System.out.println(result); in.close(); }`

}

class Point{

`int x,y; Point(int x,int y){ this.x = x; this.y = y; }`

}

pranavjain02_89 + 0 comments Thats exactly what I thought too.

joejacob + 1 comment I was thinking about transforming the coordinate matrix into a graph where the nodes would be individual sub-rows or sub-columns (defined by K consecutive cells), and the edges between nodes would simply be any two nodes that are directly adjacent to each other in the coordinate matrix. All edge lengths would be 1. From here, we can just use Djikstra's to find the shortest path from the node containing (a,b) to the node containing (c,d). The preprocessing of the graph is the bottleneck and results in an O(n^2) algorithm.

What are people's thoughts on this approach?

delamath + 1 comment O(n^2) should be necessary, as simply reading the n-by-n grid is already an O(n^2) process.

davidbgood + 0 comments I would take the entire grid as N since this is really our N size with regards to Big O. You're mixing up the convinience of using nxn to get the entire set rather than the saying the semantic (and more redundant) difference in wording of "take a square of 9 bocks, where the left is three and the right is three" as an example. The entire block is the data that you have to work with, which is n. Whatever number of times you need to traverse all of the items in n, you would then multiply by n to get nxn.

yangxiaoyong + 1 comment I don't understand this puzzle coordinate system, is bottom-left based or top-left based?

can't figure out, any one can explain ?

zo0ok + 2 comments Top left based.

00 01 02

10 11 12

20 21 22

quick_dudley + 0 comments Top left based is pretty normal, but I'm not used to seeing x mean y and y mean x.

dsujeeun + 1 comment Do I need to know graph theory to solve this problem?

jpa_beemsterboer + 1 comment Yes, it will help a tremendous amount. Basically, this is a text-book Breadth-first search (BFS) problem, that's also why this problem has been categorized within the "Queue" category, since BFS implementations rely on a Queue. Knowing Graph theory will allow you to understand the concept of Breadth or Depth-first search much quicker, it'll make much more sense.

dsujeeun + 0 comments Thank you.

cerob + 2 comments Python 3 solution using queue

from collections import deque n = int(input().strip()) gval_line = [0 for _ in range(n)] gval = [gval_line[:] for _ in range(n)] #trick [:] usage clones gval_line, otherwise one change changes all (like pointer usage) grid = [] queue = deque([]) for _ in range(n): grid.append(input().strip()) coords = [int(i) for i in input().strip().split(' ')] initial = (coords[0], coords[1]) final = (coords[2], coords[3]) queue.append(initial) while len(queue) != 0: #print(str(queue)) #print(str(gval)) #print(str(grid)) curr = queue.popleft() y, x = curr if curr == final: print(str(gval[y][x])) break cval = gval[y][x] + 1 for i in range(y+1, n): if grid[i][x] == 'X': break elif gval[i][x] == 0: gval[i][x] = cval queue.append((i, x)) for i in range(y-1, -1, -1): if grid[i][x] == 'X': break elif gval[i][x] == 0: gval[i][x] = cval queue.append((i, x)) for i in range(x+1, n): if grid[y][i] == 'X': break elif gval[y][i] == 0: gval[y][i] = cval queue.append((y, i)) for i in range(x-1, -1, -1): if grid[y][i] == 'X': break elif gval[y][i] == 0: gval[y][i] = cval queue.append((y, i))

GeoMatt22 + 1 comment I did similar, with a few tricks to shorten the code:

from collections import deque n, inf = int(input()), float('inf') grid = [list(input()) for _ in range(n)] x_beg, y_beg, x_end, y_end = map(int, input().split()) dist = [n * [inf] for _ in range(n)] dist[x_beg][y_beg], grid[x_end][y_end] = 0, '*' queue = deque([(x_beg, y_beg)]) while queue: x0, y0 = queue.popleft() d = dist[x0][y0] if grid[x0][y0] == '*': break for nbr in [range(x0+1, n), range(x0-1, -1, -1)]: for x in nbr: if grid[x][y0] == 'X': break if dist[x][y0] == inf: dist[x][y0] = d + 1 queue.append((x, y0)) for nbr in [range(y0+1, n), range(y0-1, -1, -1)]: for y in nbr: if grid[x0][y] == 'X': break if dist[x0][y] == inf: dist[x0][y] = d + 1 queue.append((x0, y)) print(d)

wxyinucas + 0 comments This is a good reference.

teja2213 + 0 comments Thanks for comment, got good idea on how to use BFS. Using visited array might have helped lot of unnecessary reprocessing.

Sort 150 Discussions, By:

Please Login in order to post a comment