L'Atelier Monstre

Gestion des entrées multiples Pour les problèmes avec plusieurs jeux de données, initialisez les variables à l'intérieur de la boucle de test pour éviter toute réutilisation indésirable des résultats précédents. Lors de l'affichage, utilisez des fonctions appropriées pour vider le tampon de sortie. Évitez les initialisations répétées de tableau ...

Problème 1 : Superficie maximale d'une île Énoncé : Étant donné une grille composée de 1 (terre) et 0 (eau), calculer la superficie maximale des îles. La superficie est le nombre total de cellules terrestres connectées horizontalement ou verticalement. Exemple d'entrée : 4 5 1 1 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1 Sortei attendue : 4 Approche ...

Rapport de résolution pour le problème P4427 [BJOI2018] Somme des profondeurs 1. Énoncé du problème La tâche principale de ce problème est la suivante : étant donné un arbre ayant le nœud 1 comme racine, il faut répondre à plusieurs requêtes. Chaque requête fournit deux nœuds u, v et un entier k, et nous devons calculer la somme des k-ièmes pui ...

L'ancêtre commun le plus proche (LCA) de deux nœuds u et v dans un arbre enraciné est le nœud le plus profond qui est un ancêtre à la fois de u et de v. Par exemple, dans l'arbre ci-dessous, LCA(3,7) = 1 et LCA(3,4) = 2. Il existe plusieurs méthodes pour calculer le LCA, classifiées en algorithmes hors ligne (toutes les requêtes sont connues à ...

L'énoncé provient de la compétition Blue Bridge Cup, problème numéro 118, intitulé "Tour de Robots". Le problème consiste à construire une structure pyramidale avec des robots de deux types ('a' et 'b') en respectant certaines règles de placement. L'approche utilisée est le parcours en profondeur (DFS) pour explorer toutes les configu ...

Problème 1 : Emplacement optimal de l'hôpital Description du problème Considérons un arbre binaire, comme illustré ci-dessous : Les valeurs dans les nœuds représentent la population des résidents, et les numéros à côté sont les identifiants des nœuds. L'objectif est de construire un hôpital sur un nœud de sorte que la somme des distances parcou ...

Cet article présente une approche pour identifier et lister toutes les composantes connexes d'un graphe non orienté en utilisant deux algorithmes de parcours fondamentaux : le parcours en profondeur (DFS) et le parcours en largeur (BFS). Description du Problème Étant donné un graphe non orienté composé de N sommets et E arêtes, le but est d'énu ...

Introduction au tri topologique : Deux approches principales existent : l'algorithme de Kahn (basé sur BFS) et la méthode DFS. Leur objectif est d'ordonner les nœuds dans un graphe dirigé acyclique (DAG), offrant souvent plusieurs solutions valides. Ces algorithmes identifient également la présence de cycles. Principe de l'algorithme de Kahn (B ...

Problème classique de recherche combinatoire avec test de primalité. #include <iostream> using namespace std; int countPrimes(int val) { if (val < 2) return 0; for (int d = 2; d * d <= val; ++d) { if (val % d == 0) return 0; } return 1; } int totalComb = 0; void generateCombinations(int step, int lastIndex, int ...

11.1 Recherche en profondeur (DFS) 11.1.1 Concepts de base Le DFS (Depth-First Search) est un algorithme récursif qui explore un chemin jusqu'au bout puis fait marche arrière. Gabarit de base void dfs(int etat) { // 1. Condition d'arrêt if (condition satisfaite) { traiter le résultat; return; } // 2. Élagage ...