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.
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.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Castle on the Grid
You are viewing a single comment's thread. Return to all 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.