Eat all apples in the maze

general
,
1

Hello All,
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 :slight_smile: Thank you!!!

My thoughts:

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.

Problem:

  • Given sizes of a matrix: N and M.
  • Given matrix itself.

Matrix contains the following values:

  1. 1s - cells where snake can go
  2. 0s - where snake can’t go
  3. 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.

2

this link might help you to solve your problem,

3

Thanks, that is what I was thinking about. Do you think that it is an efficient way to keep track of apples in ascending order and just apply this algorithm to each “supposed next” apple? one by one

4

yes this is one of the best way to solve this kind of problem