Problem 596105 · medium · Phase 05 Advanced Algorithms & Graphs

Best Harvest Walk in an Orchard

backtracking · grids · optimisation · depth-first search

An orchard is a grid trees of non-negative integers: each number is the fruit on that tree, and 0 means there is no tree (you may not step there). A picker starts at any tree, repeatedly moves up, down, left or right to another tree, picks everything on each tree visited, and never visits a tree twice. The picker may stop at any time. Return the most fruit that can be collected.

Examples

Input:  trees = [[4, 0, 2],
                 [3, 9, 0],
                 [0, 1, 5]]
Output: 22
Explanation: 4 -> 3 -> 9 -> 1 -> 5. The tree with 2 fruit is cut off.

Input:  trees = [[5]]
Output: 5

Input:  trees = [[0]]
Output: 0

Constraints

  • 1 <= len(trees), len(trees[0]) <= 5, at most 14 cells are non-zero
  • 0 <= trees[r][c] <= 100

Goals

  • Explore every simple walk from every start and keep the best total
  • Restore a cell's state after exploring from it
Starting Python…