3
0 1 0 
0 1 0
0 1 0 

3
1 0 0 
1 0 0
1 1 1

3
0 0 0
0 0 0
0 0 0

参考代码

#include<bits/stdc++.h>
using namespace std;
int a[1010][1010];
long long  dp[1010][1010][2];
int main()
{
	int n;
	cin>>n;
	int id=0;
	int cnt=0;
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)for(int k=0;k<=1;k++)dp[i][j][k]=1e9;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			scanf("%d",&a[i][j]);
			int h1=a[i][j];
			if(a[i][j]==0)
			{
				id=i;
				cnt++;
				continue;
			}
			int ans1=0;
			while(h1>0 && h1%2==0)h1/=2,ans1++;
			int h2=a[i][j];
			int ans2=0;
			while(h2>0 && h2%5==0)h2/=5,ans2++;
			dp[i][j][0]=ans1;
			dp[i][j][1]=ans2;
		}
	}
	for(int i=2;i<=n;i++)
	{
		dp[1][i][0]=dp[1][i-1][0]+dp[1][i][0];
		dp[1][i][1]=dp[1][i-1][1]+dp[1][i][1];
	    dp[i][1][0]=dp[i-1][1][0]+dp[i][1][0];
	    dp[i][1][1]=dp[i-1][1][1]+dp[i][1][1];
	}
	for(int i=2;i<=n;i++)
	{
		for(int j=2;j<=n;j++)
		{
			dp[i][j][0]=min(dp[i-1][j][0],dp[i][j-1][0])+dp[i][j][0];
			dp[i][j][1]=min(dp[i-1][j][1],dp[i][j-1][1])+dp[i][j][1];
		}
	}
	int k=0;
	if(dp[n][n][1]<dp[n][n][0])
	{
		k=1;	
	}
	if(id && dp[n][n][k]>1)
	{
		printf("1\n");
		for(int i=1;i<id;i++)printf("D");
		for(int i=1;i<n;i++)printf("R");
		for(int i=id;i<n;i++)printf("D");
		return 0;
	}
	else printf("%d\n",dp[n][n][k]);
	int i=n;
	int j=n;
	string s;
	while(1)
	{
		if(dp[i-1][j][k]<dp[i][j-1][k])
		{
			s+="D";
			i--;
		}
		else
		{
			s+="R";
			j--;
		}
		if(i==1)
		{
			while(j>1)s+="R",j--;
			break;
		}
		if(j==1)
		{
			while(i>1)s+="D",i--;
			break;
		}
	}
	int len=s.size();
	for(int i=len-1;i>=0;i--)cout<<s[i]; 
}