Nous utilisons des cookies pour améliorer votre expérience. En poursuivant votre navigation sur ce site, vous acceptez l'utilisation de cookies.


Politique de confidentialité

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

 

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

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 :

Entrée :

La première ligne contient m et n. Les n lignes suivantes contiennent m valeurs associées au nombre de pièce dans chaque case de la ligne donnée

Sortie :

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

  Exemples
Entrée du programmeSortie du programme
5 4
1 3 1 5
17 0 4 1
14 0 2 3
0 6 20 2
5 6 1 2
43
2 0
3 3
12 10 15
0 12 1
15 12 7
42
2 0

Solution 1 (Récursive)

import numpy as np
import sys

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)


m,n = map(int, sys.stdin.readline().strip().split())
pieces=[]
for i 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>

using namespace std;

int getMaxPieces(const vector<vector<int>> &pieces, int ligne, int col)
{
    int m,n;
    m=pieces.size();
    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, max(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;
        val=getMaxPieces(pieces,i,0);
        if (val > maxi){
            maxi=val;
            pos=i;
        }
    }

    pair<int,int> res;
    res.first=maxi;
    res.second=pos;
    return res;
}

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);
        }
    }

    pair<int,int> res=collectpieces(pieces);
    cout << res.first << "\n";
    cout << res.second << " 0";
    return 0;
}
                    
Complexité :
  •  Complexité temporelle : \(O(3^{m*n})\)
  •  Complexité spatiale : \(O(1)\) si l'espace de la pile de récursivité est ignoré.

Solution 2 (Programmation dynamique)

import numpy as np
import sys

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

    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)
    
    print(collected)
    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)
    


m,n = map(int, sys.stdin.readline().strip().split())
pieces=[]
for i 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>

using namespace std;
 

pair<int, int> getMaxPieces(vector<vector<int>> pieces, int m, int n)
{
    int collected[m][n];
    memset(collected, 0, sizeof(collected));
 
    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, max(droiteGauche, droiteDroite));
                                                     
        }
    }
 
    // Le maximum de pièces est la valeur maximale stockée 
    // dans la première colonne qui est le point de départ
    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;
        }
    }
    pair<int,int> ret;
    ret.first=res;
    ret.second=pos;
    
    return ret;
}
 

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);
        }
    }

    pair<int,int> res=getMaxPieces(pieces, m, n);
    cout << res.first << "\n";
    cout << res.second << " 0";
    return 0;
}
                    
Complexité :
  •  Complexité temporelle : \(O(m*n)\)
  •  Complexité spatiale : \(O(m*n)\)

Partager ce cours avec tes amis :
Rédigé par ESSADDOUKI Mostafa
ESSADDOUKI
The education of the 21st century opens up opportunities to not merely teach, but to coach, mentor, nurture and inspire.