DIFFICULTE
LIMITE DE MEMOIRE
1024 ko
LIMITE DE TEMPS
100 ms
É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.
EXEMPLE(S) D'ENTREE/SORTIE
Exemple 1
en entrée ...
2 3 0 0 1 0 0 2 1 0 1 |
-1 |
Exemple 2
en entrée ...
3 15 0 0 1 1 0 1 1 0 2 0 0 2 0 1 1 1 1 2 1 2 1 2 2 0 1 1 1 0 2 0 2 0 2 0 2 1 2 0 3 0 1 1 0 2 3 |
10 |
