Prologin
2026
Énoncé¶
Une fois la tâche accomplie, votre correspondant laisse une autre lettre pour donner rendez-vous à Joseph Marchand. Cependant, le chemin vers le point de rendez-vous est un peu délicat, car l'unique accès se fait par un pont en ruines, en proie aux algues qui prolifèrent et affaiblissent sa structure.
Joseph Marchand se situe en haut à gauche du pont, représenté par une grille de taille $\mathtt{hauteur} \times \mathtt{largeur}$. Cependant, le pont étant en ruine, il faut éviter de marcher sur les zones instables du pont.
Le pont est donc représenté par une grille, où chaque case indique
l'état actuel de la portion du pont correspondante.
Un . représente une zone sûre, et un # représente une zone qui
menace de s'effondrer.
Malheureusement, les algues prolifèrent encore, et l'état du pont ne fait que se dégrader. Après chaque pas effectué par Joseph, une nouvelle portion du pont devient subitement instable. Joseph ne doit surtout pas se trouver sur une case au moment où celle-ci devient instable, ni après.
La liste positions fragiles indique les positions qui vont devenir instables
à cause de la prolifération d'algues.
Après le premier déplacement de Joseph, la première position de la liste
indique la première case à devenir instable.
Puis, après le second déplacement de Joseph, la seconde position de la liste
indique une nouvelle case à devenir instable à son tour, et ainsi de suite.
Aidez Joseph Marchand à trouver le chemin le plus court vers son point de rendez-vous, situé dans le coin en bas à droite du pont, sans jamais marcher sur une case devenue instable.
Dans la grille, le point de départ, le coin supérieur gauche, est indiqué avec les coordonnées $(1, 1)$, et le point d'arrivée, le coin inférieur droit, est indiqué avec les coordonnées $(\mathtt{largeur}, \mathtt{hauteur})$.
Indiquez simplement la longueur du chemin le plus court, ou -1 si aucun
chemin sûr n'existe.
Entrée¶
L’entrée contiendra :
- Sur la première ligne, un entier : hauteur, le nombre de lignes de la grille.
- Sur la ligne suivante, un entier : largeur, le nombre de colonnes de la grille.
- Sur les lignes suivantes, une liste de hauteur éléments : grille, la
grille représentant l'état initial du pont (un caractère par case - '.' pour
une case libre, '#' pour une case déjà écroulée) .
- Une ligne par élément de la liste : une liste de largeur caractères juxtaposés.
- Sur la ligne suivante, un entier : N, le nombre de cases s'apprêtant à devenir instables.
- Sur les lignes suivantes, une liste de N éléments : positions
fragiles, la liste des cases qui vont devenir instables à cause de la
prolifération des algues, dans l'ordre.
- Une ligne par élément de la liste : séparés par des espaces, un entier x (la colonne de la position), et un entier y (la ligne de la position).
Sortie¶
Indiquer, sur une ligne, le temps minimal nécessaire pour Joseph afin d'atteindre le coin en bas à droite du pont depuis le coin en haut à gauche, sans jamais passer par une case fragile ou instable.
Contraintes¶
- $1 \le \mathtt{hauteur} \le 10$
- $1 \le \mathtt{largeur} \le 10$
- $1 \le N \le \mathtt{hauteur} \times \mathtt{largeur}$
- $1 \le x \le \mathtt{largeur}$
- $1 \le y \le \mathtt{hauteur}$
- $(x, y) \neq (1, 1)$
- $(x, y) \neq (\mathtt{largeur}, \mathtt{hauteur})$
- Tous les $(x, y)$ sont uniques.
- $\mathtt{grille}_{1,1} = \mathtt{'.'}$
- $\mathtt{grille}_{x,y} = \mathtt{'.'}$
- $\mathtt{grille}_{\mathtt{largeur},\mathtt{hauteur}} = \mathtt{'.'}$
Contraintes de performance¶
- $1 \le \mathtt{hauteur} \le 1\,000$
- $1 \le \mathtt{largeur} \le 1\,000$
