We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
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.
Castle on the Grid
You are viewing a single comment's thread. Return to all 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:
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.