Maximum Prize on a Falling-Ball Board
Autumn Tournament (2012)
Submission name: tvgame.cpp
Problem summary
Drop a ball into any top-row column. A dot or digit sends it down, L sends it down-left, R down-right, and X lets you choose any of those directions. Digits add their values to the prize. Find a maximum-prize route to the bottom and print one such route.
Input
N M followed by N strings of M board symbols.
Output
Maximum prize in thousands; starting column (1-based); then N−1 movement letters L, R or D.
Constraints
0 < N,M < 1000. First/last columns and the bottom row contain digits 0..9, so forced moves cannot leave the board.
Worked example
Original statement sample.
Input
4 5 1L.20 2.LX1 4L4.5 08123
Output
10 4 DRD
Solution analysis
- Every move increases the row, so the board is a directed acyclic graph. Let best[r][c] be the maximum prize obtainable starting in that cell, including its own digit if it has one. The bottom-row value is simply that digit.
- Process rows upward. For a forced symbol, add the best value of its unique successor. For X, choose the largest best value among the three cells below. Store the chosen movement letter for every non-bottom cell at the same time; these choices allow reconstruction without searching again.
- Take the maximum best value in the first row and remember its column. Follow the stored directions downward to print exactly N−1 movements. For a single-row board the route is empty, and its output line is blank.
- In the sample start in column 4, collect 2, move D to X, then R to the 5 and D to the 3. The total is 2+5+3=10 and the route is DRD.
Why it works
The bottom-row states are correct directly. Assuming the next row is solved, every legal route from the current cell must choose one permitted successor and then follow a route from it. Taking the best successor therefore gives exactly the optimal value, and its stored direction begins an optimal route. Induction upward and selection of the best start establish both value and reconstruction.
Watch out. Collect digits in the starting and bottom cells as well as intermediate cells. Forced L/R cells do not offer a choice. Print the starting column from 1. Do not print a movement out of the bottom row. Any maximizing route is accepted.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
int m;
cin>>n>>m;
vector<string>board(n);
for(string&row:board){
cin>>row;
}
vector<vector<int>>best(n,vector<int>(m,0));
vector<string>direction(n,string(m,'D'));
for(int row=n-1;row>=0;row--){
for(int column=0;column<m;column++){
char cell=board[row][column];
int reward=cell>='0'&&cell<='9'?cell-'0':0;
if(row==n-1){
best[row][column]=reward;
continue;
}
int nextColumn=column;
if(cell=='L'){
nextColumn--;
}
else if(cell=='R'){
nextColumn++;
}
else if(cell=='X'){
// Ties may be resolved arbitrarily; prefer D here.
for(int candidate=column-1;candidate<=column+1;candidate++){
if(best[row+1][candidate]>best[row+1][nextColumn]){
nextColumn=candidate;
}
}
}
best[row][column]=reward+best[row+1][nextColumn];
direction[row][column]=nextColumn<column?'L':nextColumn>column?'R':'D';
}
}
int start=0;
for(int column=1;column<m;column++){
if(best[0][column]>best[0][start]){
start=column;
}
}
cout<<best[0][start]<<'\n';
cout<<start+1<<'\n';
int column=start;
for(int row=0;row+1<n;row++){
char move=direction[row][column];
cout<<move;
if(move=='L'){
column--;
}
else if(move=='R'){
column++;
}
}
cout<<'\n';
}