Dans le cadre d'une activité de groupe, deux amis, Jean et Sophie, sont positionnés aux extrémités opposées d'une grille de M lignes et N colonnes. Jean est situé à la cellule (1, 1) (coin supérieur gauche) et Sophei à (M, N) (coin inférieur droit). Ils désirent échanger des messages. Un message de Jean à Sophie ne peut avancer que vers le bas ou vers la droite. Réciproquement, un message de Sophie à Jean ne peut se déplacer que vers le haut ou vers la gauche.

La règle essentielle est que les élèves intermédiaires de la grille ne peuvent aider au transfert qu'une seule fois. C'est-à-dire que si un élève participe au chemin "aller", il ne peut pas participer au chemin "retour", et vice-versa. Chaque élève possède un "indice de bonne volonté" (un nombre entre 0 et 100). L'objectif est de trouver deux chemins (un de (1,1) à (M,N) et un de (M,N) à (1,1)) tels que la somme totale des indices de bonne volonté des élèves rencontrés sur ces deux chemins soit maximale. Les positions de départ (1,1) et d'arrivée (M,N) sont les seuls points où les chemins peuvent se rencontrer ou se croiser.

Ce problème est un exemple classique d'optimisation de chemins doubles par programmation dynamique. Il peut être reformulé comme la recherche de deux chemins indépendants, partant tous deux de (1,1) et arrivant tous deux à (M,N), sans partager de nœuds intermédiaires. Les valeurs de bonne volonté des cellules (1,1) et (M,N) sont comptées une seule fois au total, même si les deux chemins les traversent.

Approche par Programmation Dynamique

Nous allons modéliser ce problème en utilisant une approche de programmation dynamique où l'état dp[s][r1][r2] représente la somme maximale de bonne volonté atteinte lorsque le premier messager est à la position (r1, c1) et le second messager est à la position (r2, c2). Ici, s = r1 + c1 = r2 + c2, ce qui signifie que les deux messagers ont effectué le même nombre total de pas (s-2) depuis le point de départ (1,1) et sont sur la même "diagonale" de la grille. La colonne pour chaque messager est implicitement c = s - r.

• État de la DP: dp[somme_coords][ligne_messager1][ligne_messager2].

• Initialisation:

  • Toutes les entrées de la table dp sont initialisées à une valeur très petite (par exemple, INT_MIN de <climits>) pour marquer les états inaccessibles.
  • Le cas de base est lorsque les deux messagers sont à la position de départ (1,1). La somme de leurs coordonnées est 1+1=2. La bonne volonté de cette cellule est ajoutée une seule fois : dp[2][1][1] = grille[1][1].

• **Transitions:**Pour calculer dp[s][r1][r2], nous devons considérer les quatre états précédents possibles pour la paire de messagers, puisque chaque messager peut arriver de deux directions (du haut ou de la gauche) :

  1. Le premier messager vient de (r1-1, c1) et le second de (r2-1, c2).
  2. Le premier messager vient de (r1-1, c1) et le second de (r2, c2-1).
  3. Le premier messager vient de (r1, c1-1) et le second de (r2-1, c2).
  4. Le premier messager vient de (r1, c1-1) et le second de (r2, c2-1).

  Nous prenons le maximum de ces quatre valeurs dp précédentes (en ignorant celles qui sont INT_MIN). À cette valeur maximale, nous ajoutons la bonne volonté des cellules actuelles (r1, c1) et (r2, c2). La gestion des cellules non partagées est cruciale : si (r1, c1) est la même cellule que (r2, c2) (et que ce n'est ni le point de départ ni le point d'arrivée), alors cet état est interdit et ignoré.

  La valeur à ajouter pour l'état courant est grille[r1][c1]. Si les messagers sont sur des cellules différentes (r1 != r2 ou c1 != c2), alors grille[r2][c2] est également ajouté. Si les messagers sont sur la même cellule, et que ce n'est pas la cellule d'arrivée (M,N) (car (1,1) est géré par le cas de base), alors cet état est invalide et n'est pas mis à jour.

  La somme des coordonnées s varie de 3 (pour les premières étapes après (1,1)) à M+N (pour (M,N)).

• Résultat Final: La valeur dp[M+N][M][N] représente la somme maximale de bonne volonté lorsque les deux messagers atteignent simultanément la cellule d'arrivée (M,N). La logique de calcul assure que la bonne volonté de (M,N) est comptée une seule fois.

Format d'entrée

La première ligne contient deux entiers M et N (1 ≤ M, N ≤ 50), séparés par un espace, indiquant le nombre de lignes et de colonnes de la grille.

Les M lignes suivantes contiennent N entiers chacune, représentant la grille des indices de bonne volonté. L'entier à la ligne i et colonne j (grille[i][j]) est l'indice de bonne volonté de l'élève à cette position (0 ≤ grille[i][j] ≤ 100). Les entiers de chaque ligne sont séparés par des espaces.

Format de sortie

Un unique entier : la somme maximale de bonne volonté.

Exemple

Entrée

3 3
0 3 9
2 8 5
5 7 0

Sortie

34

Code C++

#include <iostream>
#include <vector>
#include <algorithm> // Pour std::max
#include <climits>   // Pour INT_MIN

const int DIM_MAX = 55; // Dimensions maximales de la grille (M, N <= 50)
const int SOMME_COORD_MAX = DIM_MAX * 2; // Somme maximale des coordonnées (50+50 = 100)

int grille[DIM_MAX][DIM_MAX];
// dp[somme_coords][ligne_messager1][ligne_messager2]
// L'état stocke la somme maximale de bonne volonté cumulée.
int dp[SOMME_COORD_MAX][DIM_MAX][DIM_MAX]; 

int main() {
    // Optimisation des opérations d'entrée/sortie C++
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int M_lignes, N_colonnes; // M représente le nombre de lignes, N le nombre de colonnes
    std::cin >> M_lignes >> N_colonnes;

    // Lecture des indices de bonne volonté de la grille
    for (int i = 1; i <= M_lignes; ++i) {
        for (int j = 1; j <= N_colonnes; ++j) {
            std::cin >> grille[i][j];
        }
    }

    // Initialisation du tableau dp avec une valeur très petite (INT_MIN)
    // pour marquer les états comme inaccessibles ou non calculés.
    for (int s = 0; s <= M_lignes + N_colonnes; ++s) {
        for (int r1 = 0; r1 <= M_lignes; ++r1) {
            for (int r2 = 0; r2 <= M_lignes; ++r2) {
                dp[s][r1][r2] = INT_MIN;
            }
        }
    }

    // Cas de base : les deux messagers sont au point de départ (1,1).
    // La somme de leurs coordonnées est 1+1=2. La bonne volonté de (1,1) est collectée une seule fois.
    dp[2][1][1] = grille[1][1];

    // Boucle principale : itération sur la somme des coordonnées 's'.
    // 's' représente le nombre total de pas effectués par les deux messagers (hors cellule (1,1)).
    // 's' varie de 3 (première étape après (1,1)) à M_lignes + N_colonnes (pour atteindre (M,N)).
    for (int s = 3; s <= M_lignes + N_colonnes; ++s) {
        // Boucle pour la ligne du premier messager (r1)
        for (int r1 = 1; r1 <= M_lignes; ++r1) {
            int c1 = s - r1; // Calcul de la colonne correspondante pour le premier messager
            if (c1 < 1 || c1 > N_colonnes) continue; // Vérification des limites de la grille

            // Boucle pour la ligne du second messager (r2)
            for (int r2 = 1; r2 <= M_lignes; ++r2) {
                int c2 = s - r2; // Calcul de la colonne correspondante pour le second messager
                if (c2 < 1 || c2 > N_colonnes) continue; // Vérification des limites de la grille

                // Condition de non-partage de cellules intermédiaires :
                // Si les deux messagers sont sur la même cellule ET que ce n'est pas la destination finale (M,N),
                // alors cet état est invalide car les chemins ne doivent pas se croiser.
                // Le point de départ (1,1) est géré par le cas de base (s=2), donc pas concerné ici.
                if (r1 == r2 && c1 == c2 && (r1 != M_lignes || c1 != N_colonnes)) {
                    continue; 
                }

                int max_val_precedente = INT_MIN; // Pour stocker le max des 4 états précédents

                // Quatre états précédents possibles pour la paire (messager1, messager2) :
                // Chaque messager peut venir du "haut" (r-1, c) ou de la "gauche" (r, c-1).

                // 1. M1: (r1-1, c1), M2: (r2-1, c2) - les deux messagers descendent
                if (r1 - 1 >= 1 && c1 >= 1 && r2 - 1 >= 1 && c2 >= 1 && dp[s - 1][r1 - 1][r2 - 1] != INT_MIN) {
                    max_val_precedente = std::max(max_val_precedente, dp[s - 1][r1 - 1][r2 - 1]);
                }
                // 2. M1: (r1-1, c1), M2: (r2, c2-1) - M1 descend, M2 va à droite
                if (r1 - 1 >= 1 && c1 >= 1 && r2 >= 1 && c2 - 1 >= 1 && dp[s - 1][r1 - 1][r2] != INT_MIN) {
                    max_val_precedente = std::max(max_val_precedente, dp[s - 1][r1 - 1][r2]);
                }
                // 3. M1: (r1, c1-1), M2: (r2-1, c2) - M1 va à droite, M2 descend
                if (r1 >= 1 && c1 - 1 >= 1 && r2 - 1 >= 1 && c2 >= 1 && dp[s - 1][r1][r2 - 1] != INT_MIN) {
                    max_val_precedente = std::max(max_val_precedente, dp[s - 1][r1][r2 - 1]);
                }
                // 4. M1: (r1, c1-1), M2: (r2, c2-1) - les deux messagers vont à droite
                if (r1 >= 1 && c1 - 1 >= 1 && r2 >= 1 && c2 - 1 >= 1 && dp[s - 1][r1][r2] != INT_MIN) {
                    max_val_precedente = std::max(max_val_precedente, dp[s - 1][r1][r2]);
                }

                // Si un chemin valide menant à cet état a été trouvé
                if (max_val_precedente != INT_MIN) {
                    int valeur_a_ajouter = grille[r1][c1];
                    // Si les messagers sont sur des cellules différentes, ajouter la valeur de la cellule du second messager.
                    // Sinon (ils sont sur la même cellule, et nous savons que ce n'est pas une cellule intermédiaire interdite),
                    // la valeur de grille[r1][c1] (qui est grille[M][N] dans le cas final) est ajoutée une seule fois.
                    if (r1 != r2 || c1 != c2) { 
                        valeur_a_ajouter += grille[r2][c2];
                    }
                    dp[s][r1][r2] = max_val_precedente + valeur_a_ajouter;
                }
            }
        }
    }

    // Le résultat final est la somme maximale de bonne volonté lorsque les deux messagers
    // atteignent simultanément la cellule de destination (M_lignes, N_colonnes).
    // La bonne volonté de la cellule (M_lignes, N_colonnes) est ajoutée une seule fois à la fin.
    std::cout << dp[M_lignes + N_colonnes][M_lignes][N_colonnes] << std::endl;

    return 0;
}