What is the best algorithm to find the minimum number of moves to make two knights starting at some different positions meet, given that the chessboard is infinite?
At each move, both knights move simultaneously .
Currently I have this approach:
Use BFS from any one knight . Now for every cell we encounter through this BFS we can easily find the corresponding cell the other knight would be at. As the knight will meet when they both have performed same number of moves ,we need to check at each level of BFS for any cell that is reached by both the knights. This can be easily using some hash table which keeps track of visited cells.
So I'd like to know if we have a better solution.
Edit: There also exists a O(1) solution for finding the minimum number of moves to reach (x,y) from (0,0) in an infinite chessboard , Can this be used somehow for this problem ?
Currently I have this approach:
Use BFS from any one knight . Now for every cell we encounter through this BFS we can easily find the corresponding cell the other knight would be at. As the knight will meet when they both have performed same number of moves ,we need to check at each level of BFS for any cell that is reached by both the knights. This can be easily using some hash table which keeps track of visited cells.
So I'd like to know if we have a better solution.
Edit: There also exists a O(1) solution for finding the minimum number of moves to reach (x,y) from (0,0) in an infinite chessboard , Can this be used somehow for this problem ?
Read full article from (8) What is the best algorithm to find the minimum number of moves to make two knights starting at some different positions meet, given that the chessboard is infinite? - Quora
No comments:
Post a Comment