Des spéléologues ont découvert une immense galerie creusée il y a des millions d'années par une rivière souterraine. La galerie est magnifique et il a été décidé de l'ouvrir au public. Cependant, l'arrivée de nombreux visiteurs risque d'entraîner une corrosion des parois du fait d'un excès de dioxyde de carbone. Un système évolué de régénération de l'atmosphère doit donc être mis en place pour la protéger. Un certain nombre de conduits d'aération vont ainsi être percés à intervalles réguliers le long de la galerie.
On vous donne la description de la galerie sous la forme d'une grille rectangulaire de nombres, les cases de la galerie étant marquées par des 0 et les cases de roche par des 1. Le couloir de la galerie a toujours une largeur de 1 case et hormis l'entrée et la sortie, chaque case marquée par un 0 a exactement deux de ses quatre cases voisines qui sont marquées par un 0 (deux cases sont voisines si elles ont un côté en commun). L'entrée de la galerie est la case en haut à gauche de la grille, et la sortie est la case en bas à droite.
Étant donné la distance D à respecter entre chaque conduit d'aération, vous devez fournir les coordonnées de toutes les cases où creuser une aération, dans l'ordre le long de la galerie. Le premier conduit d'aération doit se trouver sur la D+1e case de la galerie en partant de l'entrée, la suivante sur la (D+1)*2e case, et ainsi de suite.
L'illustration ci-dessus représente une grille de 11 colonnes et 9 lignes. Les cercles rouges représentent les positions où placer des conduits d'aération, si le nombre de cases de galeries à laisser entre deux conduits est de 7. Ainsi, les conduits sont placés à la 8e case rencontrée en parcourant la galerie depuis l'entrée, puis à la 16e, la 24e, la 32e, et enfin la 40e.
Limites de temps et de mémoire (C++)
Temps : 1 s sur une machine à 1 GHz.
Mémoire : 16 000 ko.
Contraintes
2 <= H, L <= 1 000, où H et L sont la hauteur et la largeur de la grille,
0 <= D <= 1 000 000, où D est le nombre de cases libres à laisser entre deux conduits.
Entrée
La première ligne de l'entrée contient trois entiers : H et L, le nombre de lignes et le nombre de colonnes de la grille, puis D, la distance entre deux conduits d'aération, en nombre de cases.
Chacune des H lignes suivantes contient L entiers séparés par des espaces, représentant une ligne de la grille : 0 pour une case de galerie, 1 pour une case de roche.
Sortie
Vous devez afficher autant de lignes sur la sortie qu'il y a de conduits d'aération à placer. Chaque ligne doit contenir deux entiers : la ligne et la colonne d'un conduit d'aération, la case en haut à gauche ayant les coordonnées (0,0). Les lignes décrivent les positions dans l'ordre de parcours de la galerie.
Et France IOI n'est pas toujours clair dans ses explications. C'est quoi en haut et à gauche? J'ai déjà vu ce problème en Python. À partir de quelle position commence-t-on à compter? (0, 0)? Ou avant l'entrée? La case (0, 0) est-elle la première des D premières positions avant le puits d'aération? Ou bien est-ce que compteur doit passer de 0 à 1 à la seconde position ou de 1 à 2?
Puisque tu n'as pass de boucle dans le tracé, tu n'auras pas de backtracking à faire. Je cherche ensuite la (seule) position à 0 (array direction). Je me déplace sur la position et je la marque avec quelque chose de différent de 0 ou 1 (2 par exemple) J'avance mon compteur en accord. À mon avis, tu n'as besoin que de la fonction qui valide les coordonnées.
Ta fonction chemin récursive risque de te coûter cher. France IOI est assez strict sur le temps limite.
Ça se fait dans une boucle do ... while se terminant quand on a atteint la sortie.
Inutile d'accumuler les résultats, affiches quand tu les trouves.
Je marquerais donc (0, 0) avec un 2 et je mettrais le compteur à 1.
Je chercherais ensuite dans la boucle le suivant.
- Edité par PierrotLeFou 7 avril 2022 à 3:35:57
Le Tout est souvent plus grand que la somme de ses parties.
@rouIoude: on est dans la catégorie sur C++ Puisqu'on est au moment des révélations, voici mon code en C++ Il marche avec le test de l'exemple. (je sais, le choix de mes variables est un peu sadique) - #include <iostream> #include <array> #include <vector> bool valide(int l, int c, int L, int C) { return 0<=l && l<L && 0<=c && c<C; } int main(void) { // Je privilégie le bas et la droite même si toutes les directions sont possibles. std::array<std::array<int, 2>, 4> direction = {0, 1, 1, 0, 0, -1, -1, 0}; std::vector<std::vector<int>> galerie; int L, C, D; std::cin >> L >> C >> D; galerie.resize(L); for(int l (0); l < L; l++) { galerie[l].resize(C); for(int c (0); c < C; c++) { std::cin >> galerie[l][c]; } } int l = 0; int c = 0; int d = 1; do { galerie[l][c] = 2; int il, ic; for(auto dir: direction) { il = dir[0]; ic = dir[1]; if(valide(l+il, c+ic, L, C) && galerie[l+il][c+ic] == 0) break; } l += il; c += ic; d++; if(d == D+1) { std::cout << l << " " << c << std::endl; d = 0; } } while(l != L-1 || c != C-1); return 0; }
Le Tout est souvent plus grand que la somme de ses parties.
C'est encore trop pour ma petite tête ... J'ai fait la correction pour la définition de directions. Je ne sais pas si mon code passerait tous les tests.
edit: il ne passe pas le test 2? Est-ce que France IOI dit pourquoi?
Ne marche pas? ...
Vitesse? Ce code-ci est-il mieux?
Mémoire? Des array de dimensions maximum seraient-elles mieux? On pourrait aussi gagner en vitesse.
J'essaie d'optimiser la vittesse en choisissant au mieux l'ordre des choix des directions. - #include <iostream> #include <array> #include <vector> #include <algorithm> bool valide(int l, int c, int L, int C) { return 0<=l && l<L && 0<=c && c<C; } int main(void) { // Je privilégie le bas et la droite même si toutes les directionss sont possibles. std::array<std::array<int, 2>, 4> directions = {{{1, 0}, {0, 1}, {-1, 0}, {0, -1}}}; std::vector<std::vector<int>> galerie; int L, C, D; std::cin >> L >> C >> D; // Je favorise la dimension la plus grande, lignes vs colonnes if(C > L) { std::swap(directions[0], directions[1]); std::swap(directions[2], directions[3]); } galerie.resize(L); for(int l (0); l < L; l++) { galerie[l].resize(C); for(int c (0); c < C; c++) { std::cin >> galerie[l][c]; } } int l = 0; int c = 0; int d = 1; do { galerie[l][c] = 2; int il, ic; for(auto dir: directions) { il = dir[0]; ic = dir[1]; if(valide(l+il, c+ic, L, C) && galerie[l+il][c+ic] == 0) break; } l += il; c += ic; d++; if(d == D+1) { std::cout << l << " " << c << std::endl; d = 0; } } while(l != L-1 || c != C-1); return 0; }
- Edité par PierrotLeFou 7 avril 2022 à 19:33:20
Le Tout est souvent plus grand que la somme de ses parties.
C'est pour cela que je partage... (NB: ceci dit j'ai essentiellement adapté de code de Pierrot (=> mêmes problèmes plausibles), et ce n'est pas si compliqué à downgrader les lignes 58-60 en C++14)
EDIT/PS: quand il y a des problèmes de vitesse sur france ioi, ce n'est pas jamais un soucis d'alloc (quoique tu as été violent avec de l'allocation 2D) ou de micro-optims. C'est toujours un problème de complexité
Perso, j'ai décidé de prendre le problème sous un autre angle:
D'abord, j'ai décidé de "linéariser" la grille représentant le sous-sol, ce qui fait que, au lieu de le représenter sous la forme d'un std::vector<std::vector<in>>, je l'ai simplement représenté sous la forme d'un std::vector<int> dont la taille totale est -- dés le départ -- définie à NOMBRE_DE_LIGNES * NOMBRE_DE_COLONNES.
Cela n'a l'air de rien, mais comme nos amis de FranceIOI tiennent généralement à avoir quelque chose de rapide, cela devrait nous permettre de maintenir les données en mémoire d'une manière un peu plus "cache friendly" pour le processeur
Seulement, pour cela, il fallait disposer d'un moyen -- finalement tout simple -- afin de pouvoir déterminer l'indice dans ce tableau linéaire auquel correspond une position donnée.
Cela peut se faire très facilement avec la formule indice_recherché = LIGNE_ACTUELLE * NOMBRE_DE_COLONNES + COLONNE_ACTUELLE, formule utilisée par la fonction toIndiex de mon code
D'un autre coté, il faut aussi pouvoir récupérer la position dans la grille (en ligne et colonne) à laquelle correspond un indice donné dans le tableau linéaire.
Les deux formules à utiliser ne sont finalement pas plus compliquées que la première vu qu'elles sont respectivement
ligne_recherchée = indice_courent / NOMBRE_DE_COLONNES et
Ce sont ces deux formules qui permettent à la fonction fromIndex renvoyer une valeur correspondant à la ligne et une valeur correspondant à la colonne.
Et, parce que j'aime vraiment bien les choses "bien rangées", j'ai créé deux structures de données de base:
la structure Dimensions qui se contente de garder le nombre de lignes, le nombre de colonnes et le nombre d'éléments total que cela représente
et la structure GroundMap, qui représente le "sous-sol" tel qu'il a été cartographié
J'en ai profité, par facilité, pour garder en mémoire le nombre de "points de galeries" lorsque la carte est chargée, car cela me facilitera la vie par la suite
Puis, je me suis dit que les seuls points de la carte qui m'intéressent sont ceux où il est possible de passer, car je n'ai vraiment pas encore une âme de passe-muraille
Et, bien sur, il faut les avoir les points dans "l'ordre logique de la visite", car c'est à partir de cet ordre que l'on pourra déterminer où placer la l'aération.
Par facilité, j'ai créé une énumération représentant les quatre directions possibles me permettant d'indiquer la direction d'où vient le "point de passage précédant".
Puis j'ai créé la fonction retriveGalleries qui me permet de récupérer les "points de passage" dans l'ordre logique de la visite, et qui utilise cette notion de direction pour y arriver.
Cette fonction me renvoie un tableau d'indices qui correspondent à chaque fois à une position ligne / colonne dans la grille à laquelle se trouve un point de passage.
Une fois cette fonction créée, j'avais virtuellement déjà fini le travail, car, tout ce qu'il me restait à faire, c'était de provoquer l'affichage (sous forme de position ligne / colonne) de tous les Niemes indices de ce tableau (ou N correspond à la distance entre deux positions ventilées ).
PS: ne disposant pas de compte sur FranceIOI, et présumant en outre que ce problème n'est accessible que si on en a résolut d'autres, quelqu'un pourrait il tester mon code et me dire s'il respecte les conditions de rapidités lors des tests?
Ce qui se conçoit bien s'énonce clairement. Et les mots pour le dire viennent aisément.Mon nouveau livre : Coder efficacement - Bonnes pratiques et erreurs à éviter (en C++)Avant de faire ce que tu ne pourras défaire, penses à tout ce que tu ne pourras plus faire une fois que tu l'auras fait
@koala01: j'aime bien ton idée ... Mais tu as plusieurs fonctions. Cela ne va-t-il pas ralentir?
edit: Si j'ai bien compris ton code ... Tu as d'abord la grille de la galerie sous forme de "tableau" linéarisé à une dimension avec des indices. Puis tu génères le tableau des points de passage en indice (pas en coordonnées) Et tu parcours ce second tableau pour extraire les éléments à toutes les D positions et tu les affiches en coordonnées. Tu as finalement deux tableaux dont la dimension est sans doute moins que le double du premier mais sûrement assez longue. Je peux me demander si tu vas dépasser la limite de mémoire. On ne m'a pas dit que mon code précédent dépassait le temps limite ni la mémoire limite. J'ai décidé de converger vers ton idée. J'ai remplacé le std::vector de int en bool. On va sauver sur l'espace et être plus cache-friendly. Ce sera true si je peux passer, sinon ce sera false. Je met false sur la position que je viens de quitter. J'ai gardé les indices pour valider si je suis out of range. J'ai remplacé la fonction pour calculer l'indice par une macro. J'ai corrigé mon bug pour D==0 - #include <iostream> #include <array> #include <vector> #include <algorithm> #define index(l,c) ((l)*C+(c))
bool valide(int l, int c, int L, int C) { return 0<=l && l<L && 0<=c && c<C; }
int main(void) { // Je privilégie le bas et la droite même si toutes les directionss sont possibles. std::array<std::array<int, 2>, 4> directions = {{{1, 0}, {0, 1}, {-1, 0}, {0, -1}}}; std::vector<bool> galerie; int L, C, D; std::cin >> L >> C >> D; // Je favorise la dimension la plus grande, lignes vs colonnes if(C > L) { std::swap(directions[0], directions[1]); std::swap(directions[2], directions[3]); } galerie.resize(L*C); for(int l (0); l < L; l++) { for(int c (0); c < C; c++) { int intake; std::cin >> intake; galerie[index(l, c)] = intake == 0; } } int l = 0; int c = 0; int d = 1; if(D == 0) { d = 0; std::cout << l << " " << c << std::endl; } do { galerie[index(l, c)] = false; int il, ic; for(auto dir: directions) { il = dir[0]; ic = dir[1]; if(valide(l+il, c+ic, L, C) && galerie[index(l+il, c+ic)]) break; } l += il; c += ic; d++; if(d == D+1) { std::cout << l << " " << c << std::endl; d = 0; } } while(l != L-1 || c != C-1); return 0; }
- Edité par PierrotLeFou 8 avril 2022 à 6:49:09
Le Tout est souvent plus grand que la somme de ses parties.
@koala01: j'aime bien ton idée ... Mais tu as plusieurs fonctions. Cela ne va-t-il pas ralentir?
A mon sens, beaucoup moins que le fait de dissiper les données en mémoire du fait d'un std::vector<std::vector<:size_t>>; même si on est à la limite entre une optimisation de la logique et une micro optimisation
PierrotLeFou a écrit:
J'ai remplacé le std::vector de int en bool. On va sauver sur l'espace et être plus cache-friendly.
Je ne suis pas sur du tout que ce soit vraiment plus efficace... un bench correct serait nécessaire
PierrotLeFou a écrit:
J'ai remplacé la fonction pour calculer l'indice par une macro.
Ca, par contre, je peux être catégorique: la macro n'apporte rien, bien au contraire: elle nous fait renoncer au typage fort, et, bien que ce ne soit pas forcément un problème ici, il est toujours dommage de renoncer à une garantie en échange d'un gain tout à fait hypothétique de performances.
J'aurais, peut-être, pu déclarer la fonction inline pour forcer plus ou moins le compilateur à l'inliner tout en ayant la garantie -- du fait de sa simplicité même -- qu'elle l'aurait été.
Il serait pas mal de faire un bench pour comparer, car tu n'as malgré tout peut être pas tors ;) Mais si le gain (ou la perte) n'est pas suffisamment important(e) que pour être perceptible à l'utilisation, peut-être versons nous de nouveau dans la micro optimisation / l'optimisation prématurée?
Autant la linéarisation des donnée peut très facilement se justifier, ne serait-ce que par le fait que l'on évite grâce à elle de se retrouver avec une partie des données à gauche et l'autre partie à droite en ne nécessitant au final qu'une adaptation de la logique, autant je ne suis pas sur du tout de l'avantage réel que l'on a à passer d'un std::vector<size_t> à un std::vector<bool> ou d'utiliser une macro
Ce qui se conçoit bien s'énonce clairement. Et les mots pour le dire viennent aisément.Mon nouveau livre : Coder efficacement - Bonnes pratiques et erreurs à éviter (en C++)Avant de faire ce que tu ne pourras défaire, penses à tout ce que tu ne pourras plus faire une fois que tu l'auras fait
Je n'ai pas accès plus que toi au site France IOI et générer une grille appropriée n'est pas tout à fait évident. Quelque chose du genre à répéter? .X...X... ...X...X. xXXXXXXX. ...X...X. .X...X... C'est facile à générer à cause de la (ou les) simétrie.
Je peux générer facilement une grille 997 x 999 en Python.
Je pourrai tester macro vs fonction inline et int vs bool.
- Edité par PierrotLeFou 8 avril 2022 à 8:23:21
Le Tout est souvent plus grand que la somme de ses parties.
Pour ma part je poursuis l'idée avec une fonction récursive.
Autant mon code trouve systématiquement le chemin de la galerie, autant je ne comprends pas pourquoi il décale presque à chaque fois l'emplacement du 1er aérateur. Les suivants sont correctement placés par rapport au 1er.
Pour le moment j'imprime la grille en sortie pour plus de clarté
#include <iostream>
#include <vector>
#include <utility>
#include <array>
using Grotte = std::vector<std::vector<int>>;
std::array<std::array<int, 2>, 4> direction
{
0, 1,
1, 0,
0, -1,
-1, 0
};
int compteur{0}, count{1};
std::vector<std::pair<int, int>> sortie;
//fonctions
bool chemin(Grotte &grille, int x, int y, int olddir, int l, int c);
bool dansPlateau(int lin, int col, int l, int c);
int main()
{
std::ios::sync_with_stdio(false);
int L{0}, C{0};
std::cin >> L >> C >> compteur;
Grotte lab;
for (int l{0}; l < L; ++l)
{
for (int c{0}; c < C; ++c)
{
lab.push_back(std::vector<int>(C));
std::cin >> lab [l][c];
}
}
std::cout << "----------------------------------------\n";
if (chemin(lab, 0, 0, 0, L, C))
{
for (int i{0}; i < L; i++)
{
for (int j{0}; j < C; j++)
{
if (lab [i][j] == 7)
{
std::cout << "\033[32m" << lab [i][j] << " ";
std::cout << "\033[0m";
}
else if (lab [i][j] == 5)
{
std::cout << "\033[31m" << lab [i][j] << " ";
std::cout << "\033[0m";
}
else
{
std::cout << "\033[38m" << lab [i][j] << " ";
std::cout << "\033[0m";
}
}
std::cout << "\n";
}
for (int i{(int)sortie.size() - 1}; i >= 0; --i)
std::cout << sortie [i].first << " " << sortie [i].second << '\n';
}
return 0;
}
bool chemin(Grotte &grille, int x, int y, int olddir, int l, int c)
{
if (x == l - 1 && y == c - 1)
return true;
int nx{0}, ny{0}, i{0};
if (grille [x][y] == 0)
{
for (; i < 4; ++i)
{
if (i != (olddir + 2) % 4)
{
nx = x + direction [i][0];
ny = y + direction [i][1];
if (dansPlateau(nx, ny, l, c) && chemin(grille, nx, ny, i, l, c))
{
count++;
if (count != compteur + 1)
grille [nx][ny] = 5;
else
{
count = 0;
grille [nx][ny] = 7;
sortie.push_back({nx, ny});
}
return true;
}
}
}
}
return false;
}
bool dansPlateau(int lin, int col, int l, int c)
{
return ((lin >= 0) && (lin < l) && (col >= 0) && (col < c));
}
Bravo Pierrot, ton dernier code passe tous les tests !
En terme de vitesse, ils se valent tous, 0.22s pour les tests 9 et 10 sur la moulinette. (La moulinette donne les temps d'exécution)
Edit :
Duncan4031 a écrit:
autant je ne comprends pas pourquoi il décale presque à chaque fois l'emplacement du 1er aérateur. Les suivants sont correctement placés par rapport au 1er.
C'est parce que tu démarres de la case 0,0 et que tu as donc D-1 espaces avec la suivante alors que les suivantes ont D espace entre deux conduits.
Macro, fonction, ou fonction inline, ici il n'y aura aucune différence car tout est dans la même unité de traduction et le compilateur inlinera tout. Le plus simple pour s'en convaincre: godbolt.
Pour ce qui est de la linéarisation, je ne pense pas qu'elle apporte beaucoup car elle consiste à transformer la grille 2D en séquence 1D de coordonnées qui ne servira qu'une fois. Sur les exo de france-ioi, En général, on nous pousse à préférer le mono-passe au multi-passes, où l'on traite les données au fil de l'eau. A penser comme une itération complexe avec visitation pour le traitement à l'intérieur.
PS: le récursif peut être problématique s'il n'est pas écrit pour être "terminal" comme c'est le cas ici: le compilateur va empiler les appel de fonctions, et sur les grandes dimensions comme france-ioi ne manquera pas de faire, la pile ne sera jamais assez grande.
Pour que la récursivité soit terminale, il faut soit que le chemin renvoie une valeur, soit le résultat inaltérée de la fonction appelée de façon récursive.
PPS: Entre temps, je me suis amusé, j'ai changé la fonction de test: pas besoin de tout vérifier. Et j'ai corrigé différemment le comptage pour tout uniformiser.
#include <algorithm>
#include <array>
#include <cassert>
#include <iostream>
#include <vector>
[[noreturn]] void unreachable() { __builtin_unreachable(); }
#if 0
bool valide(int l, int c, int L, int C) {
return 0<=l && l<L && 0<=c && c<C;
}
#endif
std::array<std::array<int, 2>, 4> directions {{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}};
struct Galerie {
Galerie(std::size_t L_, std::size_t C_) : L(L_), C(C_), m_buffer(L*C) {}
Galerie(std::size_t L_, std::size_t C_, std::istream &is) : Galerie(L_, C_) {
for (std::size_t i=0; i < L*C && is >> m_buffer[i] ; ++i)
{ }
}
int const& operator()(std::size_t l, std::size_t c) const {
return m_buffer[offset(l,c)];
}
int & operator()(std::size_t l, std::size_t c) {
return m_buffer[offset(l,c)];
}
bool est_la_suite(int l, int c) const {
return /*valide(l, c, L, C)
&&*/ (*this)(l, c) == 0;
}
private:
std::size_t offset(std::size_t l, std::size_t c) const {
assert(l < L);
assert(c < C);
return c + l * C;
}
std::size_t L;
std::size_t C;
std::vector<int> m_buffer;
};
int main() {
std::size_t L, C, D;
std::cin >> L >> C >> D;
Galerie galerie(L, C, std::cin);
std::size_t l = 0;
std::size_t c = 0;
std::size_t d = 0;
while(l != L-1 || c != C-1)
{
galerie(l,c) = 2;
if (d == D) {
std::cout << l << " " << c << '\n';
d = 0;
} else {
++d;
}
#if 0
auto const wh = std::find_if(begin(directions), end(directions),
[l,c,&galerie](auto const& p){ return galerie.est_la_suite(l+p[0], c+p[1]); });
assert(wh != end(directions));
auto const [il, ic] = *wh;
l += il;
c += ic;
#else
auto find_next = [&](std::size_t & l, std::size_t & c) {
if (l > 0 && galerie.est_la_suite(l-1, c)) return --l;
if (l < L-1 && galerie.est_la_suite(l+1, c)) return ++l;
if (c > 0 && galerie.est_la_suite(l, c-1)) return --c;
if (c < C-1 && galerie.est_la_suite(l, c+1)) return ++c;
unreachable();
assert(!"should not happen");
};
find_next(l, c);
#endif
}
if(d == D) {
std::cout << l << " " << c << '\n';
}
return 0;
}
// Vim: let $CXXFLAGS='-std=c++17 -Wall -Wextra'
Pour ma part je poursuis l'idée avec une fonction récursive.
De manière générale, la récursivité est une technique particulièrement intéressante, seulement, lorsqu'elle est utilisée pour faire ce que l'on aurait pu faire avec une simple boucle, elle devient tout bonnement inutile
Déjà, parce que la technique est "compliquée" si on ne prend pas pour habitude de traiter en priorité le "cas de base" (le cas qui fera que la fonction ne sera plus rappelée), mais aussi parce que mal utilisée, elle va avoir tendance à saturer la pile d'appels, et à mener "très rapidement" le programme à planter pour cause de débordement.
Bien sur, la "figure de style" est intéressante, cependant, j'ai l'impression que cela rend le code inutilement complexe (qu'il te suffise de compter le nombre de blocs imbriqués pour t'en convaincre : tu en arrives à fermer quatre blocs imbriqués pour renvoyer false), alors qu'il y a moyen de garder le code beaucoup plus simple. Et la simplicité paye toujours, et souvent à différents points de vue, en programmation.
Ceci dit, peut être devrais tu simplement modifier un tout petit peu ta logique pour rendre le code plus "simple" (avec moins de blocs d'instructions imbriqués), en inversant le test if(grille[x][y]==0), car il est clair que, toute la logique qui suit ne peut renvoyer true que si c'est réellement le cas.
Dés lors, pourquoi ne modifierais tu pas ta logique pour renvoyer false dés qu'il est clair que c'est ce qui doit être renvoyé, ce qui te permettrait de ne renvoyer true qu'une fois que tout ce qui doit être fait aurait été effectué ?
Cela donnerait un code proche de (copié collé avec inversion de quelques tests )
#include <iostream>
#include <vector>
#include <utility>
#include <array>
using Grotte = std::vector<std::vector<int>>;
std::array<std::array<int, 2>, 4> direction
{
0, 1,
1, 0,
0, -1,
-1, 0
};
int compteur{0}, count{1};
std::vector<std::pair<int, int>> sortie;
//fonctions
bool chemin(Grotte &grille, int x, int y, int olddir, int l, int c);
bool dansPlateau(int lin, int col, int l, int c);
int main()
{
std::ios::sync_with_stdio(false);
int L{0}, C{0};
std::cin >> L >> C >> compteur;
Grotte lab;
for (int l{0}; l < L; ++l)
{
for (int c{0}; c < C; ++c)
{
lab.push_back(std::vector<int>(C));
std::cin >> lab [l][c];
}
}
std::cout << "----------------------------------------\n";
if (chemin(lab, 0, 0, 0, L, C))
{
for (int i{0}; i < L; i++)
{
for (int j{0}; j < C; j++)
{
if (lab [i][j] == 7)
{
std::cout << "\033[32m" << lab [i][j] << " ";
std::cout << "\033[0m";
}
else if (lab [i][j] == 5)
{
std::cout << "\033[31m" << lab [i][j] << " ";
std::cout << "\033[0m";
}
else
{
std::cout << "\033[38m" << lab [i][j] << " ";
std::cout << "\033[0m";
}
}
std::cout << "\n";
}
for (int i{(int)sortie.size() - 1}; i >= 0; --i)
std::cout << sortie [i].first << " " << sortie [i].second << '\n';
}
return 0;
}
bool chemin(Grotte &grille, int x, int y, int olddir, int l, int c)
{
if (x == l - 1 && y == c - 1)
return true;
int nx{0}, ny{0}, i{0};
if (grille [x][y] != 0)
return false;
for (; i < 4; ++i)
{
if (i != (olddir + 2) % 4)
{
nx = x + direction [i][0];
ny = y + direction [i][1];
if(! dansPlateau(nx, ny, l, c)
return false;
if(! chemin(grille, nx, ny, i,l,c)
return false;
count++;
grille [nx][ny] = 5;
if (count == compteur + 1)
{
count = 0;
grille [nx][ny] = 7;
sortie.push_back({nx, ny});
}
}
}
return true;
}
bool dansPlateau(int lin, int col, int l, int c)
{
return ((lin >= 0) && (lin < l) && (col >= 0) && (col < c));
}
Par contre, je trouve qu'il y a beaucoup trop de variables globales dans ton code, parce que les variables globales, C'EST MAL!!!
Enfin, une question quand même: pourquoi modifier tes valeurs d'entrées?
J'ai bien conscience que c'est rendu nécessaire par la récursivité, afin de pouvoir trouver les points déjà observés, mais ... que va-t-il se passer si on doit faire "autre chose" après avoir placé l'aération?
Ce qui se conçoit bien s'énonce clairement. Et les mots pour le dire viennent aisément.Mon nouveau livre : Coder efficacement - Bonnes pratiques et erreurs à éviter (en C++)Avant de faire ce que tu ne pourras défaire, penses à tout ce que tu ne pourras plus faire une fois que tu l'auras fait
je comprends bien que trouver une solution en récursif est plus complexe.
ici je suis dans un exercice et pour continuer mon expérience en codage, je voulais voir en récursif ce que cela fait et des difficultés qu'on rencontre.
je vais voir avec ton idée
Edit: tester à chaud le programme ne donne jamais de réponse.
int explore(Grille & grille, int l, int c, int count, int C) {
grille(l, c) = 2;
if (C +/-1 ? == count) { cout << .... ; count = 0; }
else ++ count;
if (grille.est_sortie(l, c)) return count;
find_next(grille, l, c); // cf mes réponses précédentes ; à la sortie l (X)ou c a changé
return explore(grille, l, c, count, C);
}
coté expression récursive -- ce qui est très proche de l'expression itérative.
NB: renvoyer le compteur n'apporte pas grand chose. Peut-etre avoir un vecteur des résultats que l'on empile au fur et à mesure à la place du cout.
Vu les écarts vus, je dirai qu'il n'y en a pas vraiment et que toutes les solutions se valent à ce niveau.
Et je maintiens, que quand il y a des "limites" de perfs, ça ne se joue pas à si peu.
Pour le unreachable, c'était pour assumer qu'il n'est pas censé avoir de cas hors des 4 possibles ifs. C'est pour contourner l'oubli de return. C'est dégueulasse. Juste une exploration personnelle. Ne le retient pas.
Ça serait intéressant de refaire des tests sans les sorties (std::cout) car c'est souvent un coût non négligeable. Mais France IOI n'a pas de boule de cristal pour deviner les résultats.
- Edité par PierrotLeFou 8 avril 2022 à 17:34:20
Le Tout est souvent plus grand que la somme de ses parties.
Galerie souterraine sur France IOI
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Discord NaN. Mon site.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.