很久以前就见过此题，以前看了题解，然后今天写了写，写的真搓。
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <iostream>
using namespace std;
int dp2[][];
int dp5[][];
int p2[][];
int p5[][];
int p[][];
int que[];
int x,y,n,num = ;
void f1()
{
int a,b;
a = b = n;
while()
{
if(a > &&dp2[a][b] == dp2[a-][b] + p2[a][b])
{
que[num++] = ;
a --;
}
else if(dp2[a][b] == dp2[a][b-] + p2[a][b])
{
que[num++] = ;
b --;
}
if(a == &&b == ) break;
} }
void f2()
{
int a,b;
a = b = n;
while()
{
if(a > &&dp5[a][b] == dp5[a-][b] + p5[a][b])
{
que[num++] = ;
a --;
}
else if(dp5[a][b] == dp5[a][b-] + p5[a][b])
{
que[num++] = ;
b --;
}
if(a == &&b == ) break;
}
}
void f3()
{
int a,b;
a = b = n;
while()
{
if(a > x)
{
que[num++] = ;
a --;
}
else if(b > y)
{
que[num++] = ;
b --;
}
if(a == x&&b == y) break;
}
while()
{
if(a > )
{
que[num++] = ;
a --;
}
else if(b > )
{
que[num++] = ;
b --;
}
if(a == &&b == ) break;
}
}
int main()
{
int i,j,temp,flag;
scanf("%d",&n);
flag = ;
for(i = ;i <= n;i ++)
{
for(j = ;j <= n;j ++)
{
scanf("%d",&p[i][j]);
if(p[i][j] == )
{
flag = ;
x = i;
y = j;
continue;
}
temp = p[i][j];
while(temp% == )
{
p2[i][j] ++;
temp /= ;
}
while(temp% == )
{
p5[i][j] ++;
temp /= ;
}
}
}
for(j = ;j <= n;j ++)
{
dp2[][j] = dp2[][j-] + p2[][j];
dp5[][j] = dp5[][j-] + p5[][j];
}
for(i = ;i <= n;i ++)
{
dp2[i][] = dp2[i-][] + p2[i][];
dp5[i][] = dp5[i-][] + p5[i][];
}
for(i = ;i <= n;i ++)
{
for(j = ;j <= n;j ++)
{
dp2[i][j] = min(dp2[i-][j],dp2[i][j-]) + p2[i][j];
dp5[i][j] = min(dp5[i-][j],dp5[i][j-]) + p5[i][j];
}
}
if(flag == )
{
printf("%d\n",min(dp2[n][n],dp5[n][n]));
if(dp2[n][n] < dp5[n][n])
f1();
else
f2();
}
else
{
printf("%d\n",min(,min(dp2[n][n],dp5[n][n])));
if(min(dp2[n][n],dp5[n][n]) >= )
f3();
else if(dp2[n][n] < dp5[n][n])
f1();
else
f2();
}
for(i = num-;i >= ;i --)
{
if(que[i] == )
printf("D");
else
printf("R");
}
printf("\n");
return ;
}