n × n задано матрицей field, каждая клетка которой — одно из трёх чисел:
- 0 — пустая клетка, по ней можно пройти;
- 1 — клетка с ягодой, ягоду можно сорвать и пройти дальше;
- -1 — камень, через него пройти нельзя.
Сборщик стартует в левом верхнем углу (0, 0), идёт в правый нижний угол (n - 1, n - 1), делая шаги только вправо или вниз, а затем возвращается обратно в (0, 0) шагами только влево или вверх. Ходить можно лишь по клеткам без камней. Проходя клетку с ягодой, он срывает её, и клетка становится пустой — во второй раз ягоду там не взять.
Верните наибольшее число ягод, которое можно собрать за такой путь туда и обратно. Если дойти до правого нижнего угла нельзя вовсе, ответ 0.field=[[1, 0, 1], [0, -1, 1], [1, 1, 1]] → 6
Туда идём по верхнему и правому краю и срываем 4 ягоды, обратно — по нижнему и левому краю ещё 2. Камень в центре обходим; собраны все 6 ягод поля.
field=[[0, -1], [-1, 1]] → 0
Камни перекрывают оба пути в дальний угол, поэтому собрать ничего нельзя.
field=[[1]] → 1
field=[[1, 0, 1], [0, -1, 1], [1, 1, 1]]
6
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 79 тестов на сервере, включая скрытые.