n × n field is given as a matrix field, where each cell holds one of three values:
- 0: an empty cell you can walk through;
- 1: a cell with a berry, which you can pick before moving on;
- -1: a rock that cannot be crossed.
A picker starts at the top-left corner (0, 0), walks to the bottom-right corner (n - 1, n - 1) stepping only right or down, then walks back to (0, 0) stepping only left or up. Only rock-free cells can be used. Whenever the picker passes a cell with a berry, the berry is picked and the cell becomes empty, so it cannot be picked a second time.
Return the largest number of berries the round trip can collect. If the bottom-right corner cannot be reached at all, return 0.field=[[1, 0, 1], [0, -1, 1], [1, 1, 1]] → 6
Go there along the top and right edges for 4 berries and come back along the bottom and left edges for 2 more, skirting the rock in the middle: all 6 berries on the field are collected.
field=[[0, -1], [-1, 1]] → 0
Rocks block both ways to the far corner, so nothing can be collected.
field=[[1]] → 1
field=[[1, 0, 1], [0, -1, 1], [1, 1, 1]]
6
Run checks the first 3 tests in your browser. Submit checks all 79 tests on the server, hidden ones included.