Can someone explain how do we solve this problem using BFS?[Problem - A - Codeforces]
Insert all valid places which it can go at one time from the given position in queue and maintain an matrix which tell about the no of moves taken. Update matrix value of each index as initial+1
1 Like
Formulas works pretty well for king and rook. For bishop, I have implemented BFS below where we put start point (r1, c1) in queue and keep processing elements in queue until the queue become empty or we encounter point (r2, c2).
- Pick a point x from queue and traverse its all 4 diagonals.
- For a point on any of the diagonal check visited array to check if we have already processed this point before. If not, push this point to queue with an updated distance value as : distance = distance_of_x + 1. (point x is the point which we are currently processing).
- Keep doing this until the queue is empty or you have found point r2, c2.
See the code below and feel free to ask if you still have any doubt.
1 Like
Thanks for the wonderful explanation @amanharitsh ut can you please explain how the moves are getting incremented inside the queue (i.e. line 96,101,106,111) and can you please tell the state of queue for few iteration.
lets consider r1 = 4, c1 = 4 and r2=4, c2=6.
Initially push {4, 4, 0} to q. ā0ā here means that we are already standing at point 4,4 so reaching to this point take 0 moves.
Iterations:
1st
top = {4,4,0}, pop q, so q = [] now.
from this point top you can move on diagonals like top-left (r-i, c-i) , top-right(r-i, c+i), bottom-left(r+i, c-i), bottom-right(r+i, c+i). Here āiā is in range[1,7]. Moving to any diagonal point will take 1 move because it is mentioned in the problem statement that we can move to any point diagonally in a single move. So after this operation q will be:
q = [(3, 3, 1), (3, 5, 1), (5, 3, 1), (5, 5, 1), (2, 2, 1), (2, 6, 1), (6, 2, 1), (6, 6, 1), (1, 1, 1), (1, 7, 1), (7, 1, 1), (7, 7, 1), (8, 8, 1)] -> these are all the points that can be reached in a single move from (4, 4)
2nd
pop (3, 3, 1) from q and repeat the process. 
1 Like
Thanks again! 