rt,一直WA在第31个点，想知道hack数据或者错在哪里。

思路是每次更新成功之后记录一下前缀，最后统一处理一遍路径。

#include <cstdio>
#include <algorithm>
#include <cstring>

int read() {
	int x = 0, f = 1;
	char ac = getchar();
	while (ac < '0' || ac > '9') {
		if (ac == '-')
			f = -1;
		ac = getchar();
	}
	while (ac >= '0' && ac <= '9') {
		x = (x << 3) + (x << 1) + (ac - '0');
		ac = getchar();
	}
	return x * f;
}
int n, a[1005][1005], f[1005][1005], g[1005][1005], num[1005][1005][2], pre1[1005][1005], pre2[1005][1005];
bool p;
int fx, fy;
char ans[2005];

int main() {
	n = read();
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			int now = read();
			a[i][j] = now;
			if (!now) {
				p = 1;
				fx = i;
				fy = j;
				continue;
			}
			while (now % 2 == 0) {
				num[i][j][0]++;
				now /= 2;
			}
			while (now % 5 == 0) {
				num[i][j][1]++;
				now /= 5;
			}
		}
	}
	memset(f, 0x3f, sizeof(f));
	memset(g, 0x3f, sizeof(g));
	f[1][1] = num[1][1][0];
	g[1][1] = num[1][1][1];
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (!a[i][j])
				continue;
			if (i != 1) {
				if (f[i][j] > f[i - 1][j] + num[i][j][0]) {
					f[i][j] = f[i - 1][j] + num[i][j][0];
					pre1[i][j] = (i - 2) * n + j;
				}
				if (g[i][j] > g[i - 1][j] + num[i][j][1]) {
					g[i][j] = g[i - 1][j] + num[i][j][1];
					pre2[i][j] = (i - 2) * n + j;
				}
			}
			if (j != 1) {
				if (f[i][j] > f[i][j - 1] + num[i][j][0]) {
					f[i][j] = f[i][j - 1] + num[i][j][0];
					pre1[i][j] = (i - 1) * n + j - 1;
				}
				if (g[i][j] > g[i][j - 1] + num[i][j][1]) {
					g[i][j] = g[i][j - 1] + num[i][j][1];
					pre2[i][j] = (i - 1) * n + j - 1;
				}
			}
		}
	}
	if (p) {
		if (std::min(f[n][n], g[n][n]) >= 1) {
			printf("1\n");
			for (int i = 1; i <= fx - 1; i++)
				printf("D");
			for (int i = 1; i <= fy - 1; i++)
				printf("R");
			for (int i = 1; i <= n - fx; i++)
				printf("D");
			for (int i = 1; i <= n - fy; i++)
				printf("R");
		}
	}
	if (f[n][n] < g[n][n]) {
		printf("%d\n", f[n][n]);
		int nowx = n, nowy = n, size = 0;
		while (1) {
			if (nowx == 1 && nowy == 1)
				break;
			int prex = (pre1[nowx][nowy] + n - 1) / n, prey = pre1[nowx][nowy] % n;
			if (!prey)
				prey = n;
			if (prex == nowx)
				ans[++size] = 'R';
			else
				ans[++size] = 'D';
			nowx = prex;
			nowy = prey;
		}
		for (int i = size; i >= 1; i--)
			printf("%c", ans[i]);
	} else if (g[n][n] <= f[n][n]) {
		printf("%d\n", g[n][n]);
		int nowx = n, nowy = n, size = 0;
		while (1) {
			if (nowx == 1 && nowy == 1)
				break;
			int prex = (pre2[nowx][nowy] + n - 1) / n, prey = pre2[nowx][nowy] % n;
			if (!prey)
				prey = n;
			if (prex == nowx)
				ans[++size] = 'R';
			else
				ans[++size] = 'D';
			nowx = prex;
			nowy = prey;
		}
		for (int i = size; i >= 1; i--)
			printf("%c", ans[i]);
	}
	return 0;
}