AlgoDS: Problem 2

Problem 2: Starry Field (2017/2018)

In this task we solve an optimization problem: find the optimal strategy in a simple one-player game.

We are given a rectangular grid, with a number or a star in each square. We go from the top row to the bottom row. Our path must start in the top row, and in each step go either to the square directly below the previous square, or one square to the left or right (see the picture). The score is calculated as follows.

In the first two steps, we get respectively 8 and 9 points (17 in total).
In the third step, we take a star. This does not give us any points, but increases the multiplier by 1. Score for the following numbers will be multiplied by the multiplier.
Thus, 9 in the fourth step gives us 9*2 = 18 points.
We take yet another star.
In the following five steps, we collect (9+8+8+9+4)*3 = 38*3 = 114 points.

Thus, we get 17+18+114 = 149 points by following the path on the picture. This is the highest possible score on this board.

Your task is to write a program which, given a board, finds the path which gives the highest possible score. For simplicity, it is enough to output only this highest score (you are not required to output the optimal path itself).

Testing program in C++

#include <iostream>
#include <vector>
#include <array>
#include <string>

using namespace std;

// you can add extra includes or auxiliary functions/variables if needed

int starry_field(const vector<string>& board) {
  // write your solution here
  return 90;
  }

int main() {

  vector<string> board = {
    "0587828028", 
    "2967480535", 
    "82*14606*4", 
    "*986777360", 
    "0*85524798", 
    "059*736685", 
    "084821304*", 
    "15880495*6", 
    "291*994640", 
    "13*412531*", 
    };

  int expected_result = 149;

  auto result = starry_field(board);
  cout << "Your result: " << result << "\n";
  if(result == expected_result)
    cout << "Result correct!\n";
  else
    cout << "Result incorrect!\n";
  return 0;
  }

Testing program in Python

# add your own imports and auxiliary functions if needed

def starry_field(board):
  # implement your solution here
  return 90

board = [
  "0587828028", 
  "2967480535", 
  "82*14606*4", 
  "*986777360", 
  "0*85524798", 
  "059*736685", 
  "084821304*", 
  "15880495*6", 
  "291*994640", 
  "13*412531*", 
  ]
  
expected_result = 149

my_result = starry_field(board)
print("Your result is: ", my_result)

if my_result == expected_result:
  print("Result correct!")
else:
  print("Result incorrect!")

Hints

The problem becomes easier when only the numbers are allowed (no stars). Solve this easier version first. You can get up to 60% points for an efficient solution to this.
Your solution will be tested on boards of size up to 100x100.
Use Dynamic Programming or Recursion with Memoization.

Rules

Your solution will be tested partially automatically. Please do not change the format of the parameters, the output format, or in general, parts of the testing program other than the places which are marked. (In case if your solution fails the automatic tests, I will look manually, but you might get penalty points for changing the format.)
Other programming languages are allowed, provided you have an approval of the lecturer, and write a "testing program" such as ones above yourself.
To get the full score, the time complexity of your algorithm should be at least as good as that of the intended solution.
You do not receive penalty points for bad programming style, high memory complexity, or high constant in time complexity (unless somebody really goes overboard with one of these).
Remember to test your program! The tests provided might not be sufficient.
Using the standard libraries is allowed.
Using non-standard libraries, or code snippets found in Internet, is allowed, as long as the source is given (although it should not be useful in these problems).
Discussing the algorithm and the implementation with other people is not allowed.
Send your solution to erykk@mimuw.edu.pl before Dec 17, 11:59 am (EXTENDED to Dec 20, 10:59pm).
One of the four solutions may be fixed after the deadline (but before the exam).