La collection de pièces dans un labyrinthe - Programmation compétitive

Problème de collecte de pièces — Labyrinthe

Lors du camping annuel organisé par le ministère de l'éducation pour les élèves, de nombreux jeux sont proposés pour divertir les élèves et faire de leur voyage dans le camp une expérience merveilleuse pleine de connaissances et de plaisir.

L'un des jeux préférés des élèves est la collection de pièces dans le labyrinthe, dans lequel il y a de nombreux points de départ et des boîtes contenant des pièces distribuées au hasard à l'intérieur du labyrinthe. Les élèves choisissent un point de départ et collectent des pièces.

La zone où le labyrinthe est installé a une largeur n et une hauteur m, la zone est divisée en des petits carrés de taille 1x1.

L'élève ne peut se déplacer que vers la droite, la gauche-droite et la droite-droite, comme illustré dans la figure ci-dessous :

Figure : Mouvements autorisés — droite (→), droite-gauche (↗), droite-droite (↘)

Définition — Problème de collecte de pièces Étant donné une grille de taille m × n contenant des pièces dans chaque case, on cherche le chemin de la première colonne à la dernière colonne (en se déplaçant uniquement vers la droite, diagonale haut-droite ou diagonale bas-droite) qui maximise la somme des pièces collectées.

Ce problème est un classique de la programmation dynamique (similaire au problème du "chemin le plus coûteux").

Énoncé du problème

Entrée

La première ligne contient m (hauteur) et n (largeur).
Les m lignes suivantes contiennent n valeurs associées au nombre de pièces dans chaque case de la grille.

Sortie

La première ligne contient le nombre maximum de pièces collectées.
La deuxième ligne contient deux valeurs i et j qui indiquent la position du meilleur point de départ pour maximiser le nombre de pièces (la colonne de départ est toujours 0).

Exemple 1

Entrée

Sortie

43
2 0

Explication : En partant de la ligne 2 (indexée à partir de 0), le chemin optimal collecte 43 pièces.

Exemple 2

Entrée

Sortie

42
2 0

Explication : En partant de la ligne 2, le chemin optimal collecte 42 pièces.

Contraintes

1 ≤ m, n ≤ 10²
0 ≤ pièces[i][j] ≤ 10³

Solution 1 — Approche récursive

L'idée est d'explorer récursivement tous les chemins possibles à partir de chaque case de la première colonne. Pour chaque position (ligne, colonne), on peut se déplacer vers trois directions :

Droite : (ligne, colonne+1)
Diagonale haut-droite : (ligne-1, colonne+1)
Diagonale bas-droite : (ligne+1, colonne+1)

On ajoute la valeur de la case courante et on prend le maximum des trois chemins possibles.

Arbre de récursion — Exemple simple

getMaxPieces(l=2, c=0)
├── droite → getMaxPieces(2,1)
├── droite-gauche → getMaxPieces(1,1)
└── droite-droite → getMaxPieces(3,1)

Cas de base de la récursion C++/Python

si (ligne < 0 || ligne >= m || colonne >= n) → retourner 0

import sys
import numpy as np

def getMaxPieces(pieces, ligne, col):
    m, n = pieces.shape

    if (ligne < 0) or (ligne == m) or (col == n):
        return 0
    else:
        droite = getMaxPieces(pieces, ligne, col + 1)
        droiteGauche = getMaxPieces(pieces, ligne - 1, col + 1)
        droiteDroite = getMaxPieces(pieces, ligne + 1, col + 1)
        return pieces[ligne][col] + max(droite, droiteGauche, droiteDroite)


def collectpieces(pieces):
    m, n = pieces.shape
    maxi = 0
    pos = 0
    for i in range(m):
        val = getMaxPieces(pieces, i, 0)
        if val > maxi:
            maxi = val
            pos = i
    
    return (maxi, pos)


# Lecture de l'entrée
m, n = map(int, sys.stdin.readline().strip().split())
pieces = []
for _ in range(m):
    pieces.append(list(map(int, sys.stdin.readline().strip().split())))

maxi, pos = collectpieces(np.array(pieces))
print(maxi)
print(pos, "0")

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int getMaxPieces(const vector<vector<int>> &pieces, int ligne, int col) {
    int m = pieces.size();
    int n = pieces[0].size();

    if ((ligne < 0) || (ligne == m) || (col == n))
        return 0;
    else {
        int droite = getMaxPieces(pieces, ligne, col + 1);
        int droiteGauche = getMaxPieces(pieces, ligne - 1, col + 1);
        int droiteDroite = getMaxPieces(pieces, ligne + 1, col + 1);
        return pieces[ligne][col] + max({droite, droiteGauche, droiteDroite});
    }
}

pair<int, int> collectpieces(const vector<vector<int>> &pieces) {
    int m = pieces.size();
    int maxi = -1;
    int pos = 0;
    
    for (int i = 0; i < m; i++) {
        int val = getMaxPieces(pieces, i, 0);
        if (val > maxi) {
            maxi = val;
            pos = i;
        }
    }

    return {maxi, pos};
}

int main() {
    int m, n, val;
    cin >> m >> n;
    
    vector<vector<int>> pieces(m);
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> val;
            pieces[i].push_back(val);
        }
    }

    auto [maxi, pos] = collectpieces(pieces);
    cout << maxi << "\n";
    cout << pos << " 0" << endl;
    
    return 0;
}

Sortie (Exemple 1)

43
2 0

Complexité — Solution récursive naïve Dans le pire des cas, la récursion explore de nombreux chemins redondants.
Complexité temporelle : O(3^m×n) — exponentielle.
Complexité spatiale : O(m×n) — profondeur de la pile d'appels.

Cette solution naïve recalcule plusieurs fois les mêmes sous-problèmes, ce qui la rend inefficace pour de grandes grilles.

Solution 2 — Programmation Dynamique

Le problème présente des sous-problèmes qui se chevauchent. Nous pouvons donc résoudre le problème en utilisant la programmation dynamique de bas en haut (bottom-up).

Définition — Tableau DP On crée un tableau collected[m][n] où :

collected[i][j] = nombre maximum de pièces que l'on peut collecter en partant de la case (i, j) jusqu'à la dernière colonne.

Règle de remplissage du tableau

On remplit le tableau de droite à gauche (de la dernière colonne vers la première) :

Pour la dernière colonne (j = n-1) : collected[i][n-1] = pieces[i][n-1]
Pour les autres colonnes : collected[i][j] = pieces[i][j] + max(
- collected[i][j+1] (droite)
- collected[i-1][j+1] si i > 0 (diagonale haut-droite)
- collected[i+1][j+1] si i < m-1 (diagonale bas-droite)
)

Illustration — Grille de l'exemple 1

ligne \ col	0	1	2	3
0	1	3	1	5
1	17	0	4	1
2	14	0	2	3
3	0	6	20	2
4	5	6	1	2

Tableau collected après programmation dynamique :

ligne \ col	0	1	2	3
0	32	26	9	5
1	35	13	6	1
2	43	26	8	3
3	35	34	22	2
4	26	17	8	2

collected[2][0] = 43 → maximum, donc meilleur départ à la ligne 2.

import numpy as np
import sys

def collectpieces(pieces):
    m, n = pieces.shape
    collected = np.zeros((m, n), dtype=int)

    # Remplir de droite à gauche
    for col in range(n - 1, -1, -1):
        for ligne in range(m):
            droite = 0 if (col == n - 1) else collected[ligne][col + 1]
            droiteGauche = 0 if (ligne == 0 or col == n - 1) else collected[ligne - 1][col + 1]
            droiteDroite = 0 if (ligne == m - 1 or col == n - 1) else collected[ligne + 1][col + 1]
            collected[ligne][col] = pieces[ligne][col] + max(droite, droiteGauche, droiteDroite)
    
    # Trouver le maximum dans la première colonne
    maxi = collected[0][0]
    pos = 0
    for i in range(1, m):
        if collected[i][0] > maxi:
            maxi = collected[i][0]
            pos = i
    
    return (maxi, pos)


# Lecture de l'entrée
m, n = map(int, sys.stdin.readline().strip().split())
pieces = []
for _ in range(m):
    pieces.append(list(map(int, sys.stdin.readline().strip().split())))

maxi, pos = collectpieces(np.array(pieces))
print(maxi)
print(pos, "0")

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

pair<int, int> getMaxPieces(vector<vector<int>> pieces, int m, int n) {
    int collected[m][n];
    memset(collected, 0, sizeof(collected));

    // Remplir de droite à gauche
    for (int col = n - 1; col >= 0; col--) {
        for (int ligne = 0; ligne < m; ligne++) {
            int droite = (col == n - 1) ? 0 : collected[ligne][col + 1];
            int droiteGauche = (ligne == 0 || col == n - 1) ? 0 : collected[ligne - 1][col + 1];
            int droiteDroite = (ligne == m - 1 || col == n - 1) ? 0 : collected[ligne + 1][col + 1];

            collected[ligne][col] = pieces[ligne][col] +
                                     max({droite, droiteGauche, droiteDroite});
        }
    }

    // Trouver le maximum dans la première colonne
    int res = collected[0][0];
    int pos = 0;
    for (int i = 1; i < m; i++) {
        if (collected[i][0] > res) {
            res = collected[i][0];
            pos = i;
        }
    }

    return {res, pos};
}

int main() {
    int m, n, val;
    cin >> m >> n;
    
    vector<vector<int>> pieces(m);
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> val;
            pieces[i].push_back(val);
        }
    }

    auto [maxi, pos] = getMaxPieces(pieces, m, n);
    cout << maxi << "\n";
    cout << pos << " 0" << endl;
    
    return 0;
}

Sortie (Exemple 1)

43
2 0

Complexité — Solution Programmation Dynamique

Critère	Solution récursive naïve	Programmation dynamique
Temps	O(3^m×n) — exponentiel	O(m × n) — polynomial
Espace	O(m×n) — pile d'appels	O(m × n) — tableau 2D
Sous-problèmes recalculés	Oui — nombreux recalculs	Non — mémoïsation implicite

Optimisation — Récupération du chemin

Si on veut aussi le chemin complet (pas seulement la somme maximale), on peut stocker dans un tableau supplémentaire la direction choisie pour chaque case :

// Stocker la direction (0: droite, 1: haut-droite, 2: bas-droite)
int direction[m][n];

Puis reconstruire le chemin en partant de la case de départ trouvée.

Points clés à retenir

Le problème de collecte de pièces est une variante du problème du chemin le plus coûteux dans une grille avec mouvements restreints.
La solution récursive naïve a une complexité exponentielle O(3^m×n).
La programmation dynamique permet de résoudre le problème en temps polynomial O(m × n).
L'approche dynamique remplit le tableau de droite à gauche (de la dernière colonne vers la première).
La relation de récurrence : dp[i][j] = pieces[i][j] + max(dp[i][j+1], dp[i-1][j+1], dp[i+1][j+1])
Le meilleur point de départ est la ligne qui donne la valeur maximale dans la première colonne.

Sortie

// La sortie apparaîtra ici…

Prêt · Ctrl+Entrée pour exécuter

Précédent Introduction Ã la programmation dynamique

La collection de pièces dans un labyrinthe - Programmation compétitive

Problème de collecte de pièces — Labyrinthe

Énoncé du problème

Entrée

Sortie

Solution 1 — Approche récursive

Solution 2 — Programmation Dynamique

Discussion (0)

Laisser un commentaire

Structures de données

Algorithmes

Programmation

Bases de données

CPGE

Modules informatique

La collection de pièces dans un labyrinthe - Programmation compétitive

Problème de collecte de pièces — Labyrinthe

Énoncé du problème

Entrée

Sortie

Solution 1 — Approche récursive

Solution 2 — Programmation Dynamique

Discussion (0)

Laisser un commentaire