萌新刚学dp，这道题死磕不过，Wa#22,玄关求调!

#include <bits/stdc++.h>

#define x first
#define y second
#define int long long

using namespace std;

const int N = 1010;
const int inf = 1e9;

int n;
int a[N][N];
int f[N][N], g[N][N];
int pf[N][N], pg[N][N];
pair<int, int> num[N][N];

signed main()
{
    cin >> n;
    for(int i = 1 ; i <= n ; i ++ )
        for(int j = 1 ; j <= n ; j ++ )
            cin >> a[i][j];
    int idi = -1, idj = -1;
    for(int i = 1 ; i <= n ; i ++ ) 
        for(int j = 1 ; j <= n ; j ++ )
        {
            if(a[i][j] == 0)
            {
                idi = i;
                idj = j;
                num[i][j].x = 1e9;
                num[i][j].y = 1e9;
                continue;
            }
            int tmp1 = a[i][j];
            int tmp2 = a[i][j];
            while(tmp1 % 2 == 0) num[i][j].x ++ , tmp1 /= 2;
            while(tmp2 % 5 == 0) num[i][j].y ++ , tmp2 /= 5;
        }
    memset(f, 0x3f3f3f3f, sizeof f);
    f[1][1] = num[1][1].x;
    for(int i = 1 ; i <= n ; i ++ )
        for(int j = 1 ; j <= n ; j ++ )
        {
            if(i == 1 && j == 1) continue;
            if(i == 1) pf[i][j] = 2;
            else if(j == 1) pf[i][j] = 1;
            else if(f[i - 1][j] > f[i][j - 1]) pf[i][j] = 2;
            else pf[i][j] = 1;
            f[i][j] = min((i > 1 ? f[i - 1][j] : 1e9), (j > 1 ? f[i][j - 1] : 1e9)) + num[i][j].x;
        }
    memset(g, 0x3f3f3f3f, sizeof g);
    g[1][1] = num[1][1].y;
    for(int i = 1 ; i <= n ; i ++ )
        for(int j = 1 ; j <= n ; j ++ )
        {
            if(i == 1 && j == 1) continue;
            if(i == 1) pg[i][j] = 2;
            else if(j == 1) pg[i][j] = 1;
            else if(g[i - 1][j] > g[i][j - 1]) pg[i][j] = 2;
            else pg[i][j] = 1;
            g[i][j] = min((i > 1 ? g[i - 1][j] : 1e9), (j > 1 ? g[i][j - 1] : 1e9)) + num[i][j].y;
        }
    // for(int i = 1 ; i <= n ; i ++ , cout << endl)
    //     for(int j = 1 ; j <= n ; j ++ )
    //         cout << f[i][j] << " ";
    // cout << endl;
    // for(int i = 1 ; i <= n ; i ++ , cout << endl)
    //     for(int j = 1 ; j <= n ; j ++ )
    //         cout << g[i][j] << " ";
    // cout << endl;
    // cout << endl;
    // for(int i = 1 ; i <= n ; i ++ , cout << endl)
    //     for(int j = 1 ; j <= n ; j ++ )
    //         cout << pf[i][j] << " ";
    // cout << endl;
    // for(int i = 1 ; i <= n ; i ++ , cout << endl)
    //     for(int j = 1 ; j <= n ; j ++ )
    //         cout << pg[i][j] << " ";
    int ans1 = min(f[n][n], 2 * n - 1 - f[n][n]);
    int ans2 = min(g[n][n], 2 * n - 1 - g[n][n]);
    if(min((ans1 < 0 ? 1e9 : ans1), (ans2 < 0 ? 1e9 : ans2)) > 1 && idi != -1)
    {
        cout << "1\n";
        for(int k = 2 ; k <= idi ; k ++ ) cout << "R";
        for(int k = 2 ; k <= n ; k ++ ) cout << "D";
        for(int k = idi + 1 ; k <= n ; k ++ ) cout << "R";
    }else if(ans1 < ans2 || ans2 < 0)
    {
        cout << ans1 << endl;
        int x = n, y = n;
        string str;
        while(true)
        {
            if(pf[x][y] == 2) str += 'R', y -- ;
            else str += 'D', x -- ;
            if(x == 1 && y == 1) break;
        }
        for(int i = 0 ; i < str.size() / 2 ; i ++ ) swap(str[i], str[str.size() - 1 - i]);
        cout << str;
    }else 
    {
        cout << ans2 << endl;
        int x = n, y = n;
        string str;
        while(true)
        {
            if(pg[x][y] == 1) str += 'D', x -- ;
            else str += 'R', y -- ;
            if(x == 1 && y == 1) break;
        }
        for(int i = 0 ; i < str.size() / 2 ; i ++ ) swap(str[i], str[str.size() - 1 - i]);
        cout << str;
    }
    return 0;
}