最少的末尾零路径

• 时间限制：2 秒
• 内存限制：64 MiB

题目描述

给定一个由非负整数组成的 $n\times n$ 方阵。请从左上角出发，每一步只能向右或向下，最终到达右下角。

将路径上经过的所有数相乘。你需要使乘积末尾连续的零尽可能少，并输出最小数量以及任意一条达到最优值的路径。

若路径乘积为 $0$，按本题约定其末尾零数量视为 $1$。

输入格式

第一行一个整数 $n$。接下来 $n$ 行每行包含 $n$ 个非负整数。

输出格式

第一行输出最少的末尾零数量。第二行输出长度为 $2n-2$ 的路径字符串，其中 D 表示向下，R 表示向右。

若有多条最优路径，输出任意一条即可。

样例输入 1

3
1 2 3
4 5 6
7 8 9

样例输出 1

0
DDRR

数据范围

对于所有数据，$2\le n\le1000$，$0\le a_{i,j}\le10^9$。