Some coins are spread in the cells of an \(n\times m\) board, one coin per cell, as shown in the figure below:

A robot, located in the upper left cell of the board, needs to collect as many of the coins as possible and bring them to the bottom right cell. On each step, the robot can move either one cell to the right or one cell down from its current location. When the robot visits a cell with a coin, it picks up that coin.

Design and implement an algorithm to find the maximum number of coins the robot can collect and a path it needs to follow to do this.

Assignment

Write a Python function collect(matrix: list) that takes a matrix consisting of zeroes and ones as argument, and returns a string containing the characters \(→\) and \(↓\). (If your keyboard doesn’t contain these characters yet, you can simply copy them from here.)

Example

>>> collect([[0, 0, 1, 0, 0, 0], [0, 0, 1, 0, 1, 0], [0, 0, 0, 1, 0, 1], [1, 1, 0, 0, 0, 1], [0, 1, 0, 0, 1, 0], [0, 0, 0, 1, 1, 0]])
"→→↓→→→↓↓↓↓"