Путешествие по сетке (Grid Journey)
Вам дана сетка размером n x n, и ваша задача — найти все пути, которые ведут из левого верхнего угла в правый нижний угол этой сетки.
В данной сетке можно перемещаться только вниз или вправо. Каждая ячейка в сетке может быть либо пустой (0), либо заблокированной (1). Нельзя проходить через заблокированные ячейки. Ваша цель — найти все возможные маршруты из левого верхнего угла к правому нижнему углу, двигаясь только вниз или вправо.
Входные данные
Первая строка содержит одно целое число n (1 ≤ n ≤ 10), обозначающее размер сетки. Следующие n строк содержат по n целых чисел, разделённых пробелами: 0 (пустая ячейка) или 1 (заблокированная ячейка), описывающих каждую ячейку сетки.
Выходные данные
Выведите все маршруты из левого верхнего угла к правому нижнему углу, учитывая только пустые ячейки. Каждый маршрут следует выводить в отдельной строке. Каждый маршрут представляется последовательностью символов D (движение вниз) и R (движение вправо). Порядок вывода путей не имеет значения.
Примеры
Входные данные | Выходные данные |
3
0 0 1
0 0 0
0 1 0 | RDRD
DRRD |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB