Piège Courant

Une erreur fréquente est de minimiser simultanément les facteurs 2 et 5 durant le parcours. Considérons cette grille :

2
1 125
10 8

Un chemin minimisant le minimum des deux facteurs produirait 3 zéros finaux, tanddis que la solution optimale n'en a que 2.

Solution Optimale

Définissons deux matrices DP :

• dp_deux[i][j] : somme minimale de facteurs 2 du chemin (1,1) à (i,j)
• dp_cinq[i][j] : somme minimale de facteurs 5 du même chemin

Les transitions s'effectuent par comparaison des cases supérieure et gauche :

dp_deux[i][j] = min(dp_deux[i-1][j], dp_deux[i][j-1]) + facteurs2[i][j]
dp_cinq[i][j] = min(dp_cinq[i-1][j], dp_cinq[i][j-1]) + facteurs5[i][j]

Le résultat final est le minimum entre dp_deux[n][n] et dp_cinq[n][n].

Gestion des Valeurs Nulles

Si une cellule contient 0, le produit final est 0 (1 zéro final). Si le minimum calculé dépasse 1, on privilégie un chemin passant par un 0 :

8 125 24
2025 12 12
0 56 425

Ici, la solution standard donnerait 3 zéros, mais le chemin via 0 produit 1 zéro.

Implémentation

#include<iostream>
#include<climits>
using namespace std;

const int MAX = 1005;

struct Facteurs {
  int deux, cinq;
  char dir_deux, dir_cinq;
};

Facteurs compterFacteurs(int x) {
  if (x == 0) return {0, 0};
  int d = 0, c = 0;
  while (x % 2 == 0) d++, x /= 2;
  while (x % 5 == 0) c++, x /= 5;
  return {d, c};
}

int main() {
  int n, x_zero = -1, y_zero = -1;
  bool zero_present = false;
  cin >> n;
  
  Facteurs grille[MAX][MAX], dp[MAX][MAX];
  
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      int val;
      cin >> val;
      if (val == 0) {
        zero_present = true;
        x_zero = i;
        y_zero = j;
      }
      grille[i][j] = compterFacteurs(val);
    }
  }

  // Initialisation des bords
  for (int i = 0; i <= n; i++) {
    dp[i][0] = {INT_MAX, INT_MAX, 0, 0};
    dp[0][i] = {INT_MAX, INT_MAX, 0, 0};
  }
  dp[1][1] = grille[1][1];

  // Remplissage DP
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (i == 1 && j == 1) continue;
      
      Facteurs haut = dp[i-1][j];
      Facteurs gauche = dp[i][j-1];
      
      if (haut.deux < gauche.deux) {
        dp[i][j].deux = haut.deux + grille[i][j].deux;
        dp[i][j].dir_deux = 'D';
      } else {
        dp[i][j].deux = gauche.deux + grille[i][j].deux;
        dp[i][j].dir_deux = 'R';
      }
      
      if (haut.cinq < gauche.cinq) {
        dp[i][j].cinq = haut.cinq + grille[i][j].cinq;
        dp[i][j].dir_cinq = 'D';
      } else {
        dp[i][j].cinq = gauche.cinq + grille[i][j].cinq;
        dp[i][j].dir_cinq = 'R';
      }
    }
  }

  // Traitement du zéro
  if (zero_present && min(dp[n][n].deux, dp[n][n].cinq) > 1) {
    cout << "1\n";
    for (int i = 1; i < y_zero; i++) cout << 'R';
    for (int i = 1; i < n; i++) cout << 'D';
    for (int i = y_zero; i < n; i++) cout << 'R';
    return 0;
  }

  // Reconstruction du chemin
  int total_zeros = min(dp[n][n].deux, dp[n][n].cinq);
  cout << total_zeros << '\n';
  
  string chemin = "";
  int i = n, j = n;
  bool modeDeux = (dp[n][n].deux <= dp[n][n].cinq);
  
  while (i > 1 || j > 1) {
    char dir = modeDeux ? dp[i][j].dir_deux : dp[i][j].dir_cinq;
    chemin = dir + chemin;
    (dir == 'D') ? i-- : j--;
  }
  
  cout << chemin;
  return 0;
}