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 programme | Sortie 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)\)
