Prologin, le concours national d'informatique

Énoncé¶

Joseph Marchand et son nouvel allié connaissent dès à présent l'emplacement de la tour de contrôle ciblée ! Ils tentent alors de s'y rendre de toute urgence. Cependant, des travaux leur barrent la route ! Heureusement, Joseph Martial, dirigeant de la ville, peut intervenir pour libérer le chemin.

La ville est représentée par une grille de $\mathtt{hauteur}$ lignes et $\mathtt{largeur}$ colonnes. Chaque case de la grille est soit une case libre, soit un mur.

Joseph et sa bande se situent à l'extrémité en haut à gauche de la ville, de coordonnées $(1, 1)$, et la tour de contrôle se situe en bas à droite de la ville, aux coordonnées $(\mathtt{largeur}, \mathtt{hauteur})$. La ville est dite juste s'il existe un chemin reliant les deux points d'intérêt en ne passant que par des cases libres, allant de case en case adjacentes (diagonales interdites).

$P$ projets de construction doivent être considérés dans l'ordre. Un projet de construction représente une tentative de rajouter un mur sur une case de la ville. Pour chaque projet de construction, dans l'ordre :

Si la case correspondante contient déjà un mur, ou que la ville resterait juste après l'ajout du mur dans la case correspondante, Joseph Martial autorise la construction du mur, car cela n'empêcherait pas nos amis d'atteindre la salle de contrôle. On affiche alors PERMIS. Le mur est alors construit et reste en place dans la considération des prochains projets de construction.
Au contraire, si la construction du mur aurait empêché de relier les deux points d'intérêt, Joseph Martial empêche alors la construction du mur. On affiche alors INTERDIT. On doit donc, par exemple, interdire tout projet de construction sur les cases $(1, 1)$ ou $(\mathtt{largeur}, \mathtt{hauteur})$.

Aidez Joseph à déterminer s'il doit accepter ou refuser chaque projet de construction.

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 la ville (un caractère par case - '.' pour un passage libre, '#' pour un mur).
- Une ligne par élément de la liste : une liste de largeur caractères juxtaposés.
Sur la ligne suivante, un entier : P, le nombre de projets à tester.
Sur les lignes suivantes, une liste de P éléments : projets, la liste des projets à tester.
- Une ligne par élément de la liste : séparés par des espaces, un entier x (la colonne du projet), et un entier y (la ligne du projet).

Sortie¶

Pour chaque projet testé, afficher sur une nouvelle ligne INTERDIT si placer un mur à cette position bloque tout chemin possible entre le coin supérieur gauche et le coin inférieur droit de la grille, PERMIS sinon. Un chemin n'est possible qu'en se déplaçant horizontalement ou verticalement, et ne peut pas passer à travers les murs.

Contraintes¶

$1 \le hauteur \le 50$
$1 \le largeur \le 50$
$1 \le P \le 50$
$1 \le x \le largeur$
$1 \le y \le hauteur$

Contraintes de performance¶

$1 \le hauteur \le 1\,000$
$1 \le largeur \le 1\,000$
$1 \le P \le 20\,000$

Contraintes d'exécution

Utilisation mémoire maximum: 100000 kilo-octets
Temps d'exécution maximum: 1000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée

4
5
.#...
...#.
..#..
.....
5
1 3
1 4
2 3
5 1
4 4

Exemple de sortie

PERMIS
PERMIS
PERMIS
INTERDIT
PERMIS

Commentaire

Ici, la grille fait 4 lignes et 5 colonnes. On a 5 projets de construction à étudier.

Le premier se trouve en 3$^e$ ligne 1$^{ère}$ colonne. Cela n'empêche pas de relier les deux points d'intêret. On affiche donc PERMIS.
Le deuxième se trouve en 4$^e$ ligne 1$^{ère}$ colonne. Cela n'empêche pas de relier les deux points d'intêret. On affiche donc PERMIS.
Le troisième se trouve en 3$^e$ ligne 2$^e$ colonne. Cela n'empêche toujours pas de relier les deux points d'intêret. On affiche donc PERMIS.
Le quatrième se trouve en 1$^{ère}$ ligne 5$^e$ colonne. Ici, on voit que le chemin se retrouve bloqué entre les deux points d'intêret. On empêche donc sa construction, et on affiche INTERDIT.
Enfin, le dernier se trouve en 4$^e$ ligne 4$^e$ colonne. Cela n'empêche pas de relier les deux points d'intêret. On affiche donc finalement PERMIS.