ROBOT

from typing import List, Tuple, Any
import random

def print_mx(mx:List[List[int]]):
    for i in mx:
        for j in i:
            print(f"{j:3d}", end = " ")
        print()

def main():

    mx = [
            [0,0,0,20,0,0],
            [1,0,3,0,5,0],
            [0,0,0,0,5,0],
            [10,1,0,0,0,0],
            [0,0,11,7,0,0],
        ]
    print_mx(mx)
    print()
    dp = [[0] * len(mx[0]) for _ in range(len(mx))]

    dp[0][0] = mx[0][0]

    for i in range(1, len(mx[0])):
        dp[0][i] = dp[0][i-1] + mx[0][i]

    for i in range(1, len(mx)):
        dp[i][0] = dp[i-1][0] + mx[i][0]

    for i in range(1, len(mx)):
        for j in range(1, len(mx[0])):
            dp[i][j] = mx[i][j] + max(dp[i-1][j], dp[i][j-1])

    print_mx(dp)
    ls = []
    i,  j = len(mx) - 1, len(mx[0]) - 1

    while i > 0 and j > 0:

        if dp[i-1][j] >= dp[i][j-1]:

            ls.append("Down")
            i -= 1

        else:

            ls.append("Right")
            j -= 1

    while i == 0 and j > 0:

        ls.append("Right")
        j -= 1

    while j == 0 and i > 0:
        ls.append("Down")
        i -= 1

    ls = ls[::-1]

    for step in ls:
        print(step, end = " ")

    print(dp[-1][-1])




if __name__ == "__main__":
    main()