Бизнес-классики, реализация задачи

[IgorZ1992]

Доброго времени суток, прошу помощи по решению задачи,а именно в помощи написанию реализации, мне не ясно: Каким образом можно собрать максимальное кол-во денег(есть ли какой-то алгоритм по проходу матрицы который позволит это осуществить),можно ли пройти матрицу с помощью комбинации вертикальной и горизонтальной змейки? если да, то каким образом нужно построить алгоритм чтобы он гарантированно находил решение?
Может ли кто-то дать наводки как стоит сделать решение?

Задача следующая:
Поле для игры в бизнес-классики представляет собой прямоугольник, состоящий из 3 * N клеток. В некоторых клетках лежит по одному рублю, в остальных - ничего нет. Играющий выбирает для начала игры одну из трех левых клеток и прыгает в нее. За один ход играющий перепрыгивает в одну из клеток, имеющих общую сторону с той, в которой он находится. При этом запрещено прыгать в те клетки, в которых он уже побывал. При очередном прыжке все деньги, собранные к этому моменту, удваиваются, а затем, если в новой клетке лежит рубль, то он прибавляется к имеющейся сумме денег. Считается, что в начале игры денег у играющего нет. Закончить прыжки надо в одной из трех правых клеток поля и при этом заработать как можно больше денег.

Требуется написать программу, которая по известному значению N и расположению рублей в клетках находит такую последовательность прыжков, при которой играющий заработает наибольшее количество денег. Если таких последовательностей несколько, то следует выбрать любую последовательность, количество прыжков в которой минимально.

Входные данные:
В первой строке входного файла с именем CLASS.IN записано натуральное число N (1 < N < 80). В каждой из последующих трех строк находится N чисел (0 или 1), описывающих расположение рублей в клетках первой, второй и третьей строки игрового поля соответственно. Единица обозначает наличие рубля в клетке, ноль - его отсутствие. Числа в каждой из этих трех строк входного файла расположены через пробел.

Выходные данные:
Выходной файл с именем CLASS.OUT должен содержать 2 строки. В первой строке должен находиться номер строки игрового поля (1, 2 или 3), с которой играющему следует начать игру. Вторая строка файла должна описывать последовательность прыжков. Каждый прыжок в этой последовательности нужно обозначить одним из следующих символов:

U - если в результате прыжка номер строки, на которой находится играющий, уменьшился на 1;
D - если номер строки увеличился на 1;
L - если номер столбца уменьшился на 1;
R - если номер столбца увеличился на 1.

Символы во второй строке выходного файла должны быть выведены без пробелов.

Пример входного файла:

4
1 1 1 0
1 1 1 0
1 1 1 1

Пример выходного файла для приведенного примера входного файла:
1
DDRUURDDRUU