The least round way

#include<bits/stdc++.h>
using namespace std;
const int N = 1100;
typedef pair<int, int> PII;
int a[N][N];
int f[N][N][3];

int main() {
	int n;
	cin >> n;
	PII  z = {-1, -1};
	
	for (int i = 1; i <= n; i ++) {
		for (int j = 1; j <= n; j ++) {
			cin >> a[i][j];
			if (a[i][j] == 0) {
				z = {i, j};
				continue;
			}
			int cnt = 0;
			while (a[i][j] % 2 == 0) {
				cnt ++;
				a[i][j] /= 2;
			}
			f[i][j][1] = cnt;
			cnt = 0;
			while (a[i][j] % 5 == 0) {
				cnt ++;
				a[i][j] /= 5;
			}
			f[i][j][2] = cnt;
		}
	}
    
    //为了防止选到矩阵外，先算第一行和第一列
	for (int i = 2; i <= n; i++) {
			f[i][1][1] += f[i - 1][1][1];
			f[i][1][2] += f[i - 1][1][2];
	
			f[1][i][1] += f[1][i - 1][1];
			f[1][i][2] += f[1][i - 1][2];
		}
		
	for (int i = 2; i <= n; i ++) {
		for (int j = 2; j <= n; j ++) {
			f[i][j][1] += min(f[i - 1][j][1], f[i][j - 1][1]);
			f[i][j][2] += min(f[i - 1][j][2], f[i][j - 1][2]);
		}
	}
	int res = f[n][n][1] > f[n][n][2] ? 2 : 1;
    
	//有零特判
	if (z != make_pair(-1, -1) && f[n][n][res] > 0) {
		cout << 1 << endl;
		for (int i = 1; i < z.first; i ++) {
			cout << "D";
		}
		for (int j = 1; j < n; j ++) {
			cout << "R";
		}
		for(int i = z.first; i < n; i ++)
		{
			cout << "D";
		}
		return 0;
	}
	cout << min(f[n][n][1], f[n][n][2]) << endl;
	string s = "";
	int i = n, j = n;
    
    //根据2和5中最小的那个来选择路径
	while (1) {
		if (f[i - 1][j][res] < f[i][j - 1][res]) {
			i --, s += 'D';
		} else {
			j --, s += 'R';
		}

		if (i == 1) {
			for (int k = j - 1; k > 0; k --)s += 'R';
			break;
		}
		if (j == 1) {
			for (int k = i - 1; k > 0; k --)s += 'D';
			break;
		}
	}
	
	for (int i = s.size() - 1; i >= 0; i --) {
		cout << s[i];
	}
	return 0;
}