Prologin
2025
ÉNONCɶ
Joseph Marchand s'est mis sur le marché très lucratif des jeux pour iPhone. Il a décidé de programmer un jeu de labyrinthe en 3D.
Pour cela, il commence par générer un labyrinthe carré de N par N au hasard : il part d'une situation où chaque case est entouré de 4 murs et il abat des murs au fur et à mesure. Malheureusement, il ne sait pas trop quand arrêter son programme pour que dans son labyrinthe, il y ait au moins un chemin entre toute paire de cases.
On vous donne l'entier N, puis un entier M suivi de M coordonnées de murs que Joseph veut abattre (sous la forme « c l k », un triplet sur chaque ligne, avec c et l coordonnées (colonne et ligne) d'une case entre 0 et (n - 1), et k la direction du mur à abattre : 0 = nord, 1 = est, 2 = sud, 3 = ouest) dans l'ordre. Vous devez renvoyer -1 si abattre tous ces murs ne suffira pas à assurer la connexité du labyrinthe, ou le plus petit entier i possible tel qu'en abattant tous les murs de 0 à i, le labyrinthe est devenu connexe.
ENTRÉE¶
- Un entier N.
- Un entier M.
- Sur les M lignes suivantes, trois entiers « c l k ».
LIMITES¶
- N <= 100, M <= 4 * N * N.
SORTIE¶
- L'entier défini ci-dessus.