Construction de labyrinthe – Regional event 2010

Level 6

É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.

Runtime constraints

Maximum memory usage
1024 kilobytes
Maximum execution time
100 milliseconds

Input/output samples

Sample input
2
3
0 0 1
0 0 2
1 0 1
Sample output
-1
Sample input
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
Sample output
10

Submit your solution

You have to register or log in to be able to submit your solution.