Prologin, the French National Computer Science Contest

Énoncé¶

Les vélociraptors se sont échappés de leurs cages ! Ils errent librement, tandis que les chercheurs se sont dispersés pour se cacher aux quatre coins du laboratoire.

Vous vous réfugiez dans la salle de contrôle, où vous repérez vos collègues et les dinosaures grâce aux caméras de surveillance. Une console vous permet aussi de fermer définitivement des portes blindées à travers le laboratoire, bloquant le passage à tout individu et toute créature.

Vous devez agir vite afin de libérer les chercheurs. Les vélociraptors sont extrêmement rapides et perceptifs, si bien qu'au moindre bruit, ils seront sur leur proie avant même qu'elle ait fait un pas. Votre seule chance est d'enfermer les prédateurs d'un coup grâce aux portes blindées.

Étant donné le plan du laboratoire, composé d'espaces vides . de murs #, et de portes blindées ? initialement ouvertes, et contenant des chercheurs c et des vélociraptors v, vous devez déterminer s'il est possible d'empêcher les vélociraptors de sortir et de permettre à tous les chercheurs de s'échapper.

Les chercheurs et les vélociraptors peuvent se déplacer horizontalement et verticalement, mais pas en diagonale. Ils peuvent sortir par n'importe quel espace vide ou porte ouverte au bord du plan.

Entrée¶

L'entrée comprendra :

sur la première ligne, les dimensions m et n du bâtiment ;
sur les m lignes suivantes, le plan du laboratoire.

Sortie¶

Vous afficherez en sortie :

1 si vous pouvez enfermer les vélociraptors et permettre aux chercheurs de s'enfuir ;
0 sinon.

Contraintes¶

1 ≤ m, n ≤ 100

Il y a au moins un chercheur et un vélociraptor dans le bâtiment.

Runtime constraints

Maximum memory usage: 1000 kilobytes
Maximum execution time: 1000 milliseconds

Input/output samples

Sample input

6 21
#####################
#.c.#..v#...#...#...#
#...#...#v..#.v.#..v#
##?###?###?###?###?##
#...c...............?
#####################

Sample output

Note

Vous enfermez les vélociraptors et vous échappez avec votre collègue.