A simple BFS but we need to be a little clever. Remember how we were doing it? we were starting form a certain node and our wave was passing over all the nodes and the node was the closest, and there is no other path which is shorter than the one we found on the current way, In our case instead of starting from each node all over again we can start from all the '1' nodes which will generate us the same answer. for more details look at the source code/
No comments:
Post a Comment