# Castle on the Grid

# Castle on the Grid

- BH
codeharrier + 1 comment Hard to believe this was only 30 points.

HemanthKumar + 0 comments agree

mcr431 + 1 comment Test case 12:

3

. . .

. X .

. X .

2 0 0 2

How does this equal 3???

- SL
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 :).

- PV
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.

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

ianbibby + 2 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.

- BG
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.

- S
ShubhamV06 + 0 comments Thank you very much! :D

- _S
_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.

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

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

- LC
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 + 2 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.

- GD
giridarantce + 0 comments yes same for me

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

- JJ
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 ?

- GT
zo0ok + 2 comments Top left based.

00 01 02

10 11 12

20 21 22

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

- A
cerob + 1 comment 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))

- MW
GeoMatt22 + 0 comments 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)

- AH
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; }`

}

- PJ
pranavjain02_89 + 0 comments Thats exactly what I thought too.

dsujeeun + 0 comments Do I need to know graph theory to solve this problem?

Sort 87 Discussions, By:

Please Login in order to post a comment