King Labyrinth

Question

I train for programming competitions, and I turn to complex problems that I could not answer in the past. One of them was the labyrinth king. Essentially, you are given an array of NxN numbers -50<x<50 , which are tokens. You should start at position 1.1 (I assume that 0.0 is in the index of the array) and end with N, N. You must pick up the tokens in the cells you are visiting, and you cannot step on a cell without a marker (represented by 0 ) If you are surrounded by 0, you lose. If there is no solution in the maze, you display "No solution." In addition, you print the maximum possible amount that you can get by adding the tokens that you receive.

I do not know how to solve this problem. I decided that you can write a labyrinth algorithm to solve it, but it takes time, and in programming contests you are given only two hours to solve several problems. I guess there is some kind of pattern that I am missing. Does anyone know how I should approach this?

In addition, it may help to mention that this problem is for high school students.

Answer 1

This type of problem is usually solved by dynamic programming or memoization .

Basically you formulate a recursive solution and solve it from the bottom up while remembering and reusing previously calculated results.

Answer 2

A simple approach (i.e. the simplest for the code) is to try all possible paths - try every first step; for every first step, try every second step; for each combination of the first step / second step, try every third stage; and so on. However, depending on how large the maze is, this may take too much time (or it may not be so).

Your next step is to think about how you can do it faster. The first step, as a rule, is to eliminate moves that, as you know, cannot lead to the finish line or cannot lead to the finish line with higher points than the one you already have. Since this is a practice for competitions, we will leave you to do this work yourself.

Answer 3

Think Graph Algorithms: Algorithm Design Guide