I’ve just started to learn how to solve competitive problems. I met such a problem, but not sure what would be a right way to solve it. Would really appreciate if you can help with that Thank you!!!
I already solved one problem using BFS for finding the shortest path from start of maze to the end, but not sure if that algorithm would be useful for solving this problem as well.
I would keep coordinates of apples in the binary search tree (e.g. node 2 would contain all coordinates of apples with size 2). Then I would apply in-order traversal through this BST finding shortest paths to the next apple using BFS. If there are many coordinates contained in one node (e.g. 2), compare and choose the shortest path to the next apple. Does it sound correct? I just believe that there is an easier solution.
- Given sizes of a matrix: N and M.
- Given matrix itself.
Matrix contains the following values:
- 1s - cells where snake can go
- 0s - where snake can’t go
- bigger than 1 - cells with apple sizes
Snake should eat all the apples in ascending order (2s, 3s, 4s, etc.) Multiple apples could have the same size.
Find the shortest path to do that. Return -1 if snake can’t finish all the apples.