九度Online Judge

OJ新增积分机制,如有任何问题或者建议,请发帖到九度论坛OJ意见反馈版,祝大家一切顺利!
亲,九度OJ官方微博开通了,欢迎你来粉!微博地址:weibo.com/jobdu

 题目1396-九度Online Judge,用代码记录你的成长之路!

题目1396:最少零的路径

时间限制:1 秒

内存限制:32 兆

特殊判题:

提交:462

解决:52

题目描述:

一个由非负整数构成的N * N大小的矩阵,你需要按照如下的规则找到一条访问路径:

     1、起点为该矩阵的最左上角元素

     2、终点为该矩阵的最右下角元素

     3、在遍历过程中,只允许从当前的单元移动到与之相邻的右侧单元或者下方单元

 

最后,当我们按照如上三个规则获取路径之后,我们会将所访问到的单元中的数字相乘,同时希望得到的乘积末尾所含有的连续0的个数最少。找出这么一条路径,输出其对应的末尾0的个数及遍历的过程。其中往下走,则用D表示(Down);往右走,则使用R表示(Right),看Sample能帮助你理解。

注意:该题为Special Judge,符合要求的路径会有多条,只需要输出你认为正确的答案即可。

输入:

每个测试文件包含多个测试案例,每个测试案例包含两个部分:

第一行为整数N,代表该矩阵的大小。其中(1 <= N <= 1000)。

接下来会有N行,每行为N个非负整数,代表这个N*N矩阵中的所有元素。所有元素的大小都不会超过10^9。

输出:

对于每个测试案例,输出两行。第一行为一个整数,代表所得路径中元素相乘获得末尾连续0的个数;第二行则是由D和R组成的字符串,代表对应的那条路径。

样例输入:
2
1 2
5 6
2
1 2
2 5
样例输出:
0
RD
1
DR
答疑:
解题遇到问题?分享解题心得?讨论本题请访问:http://t.jobdu.com/thread-8119-1-1.html