Tower Defense – Regional event 2009

Level 3

ENONCE

Nous nous proposons ici d'écrire une fonction nous permettant de dire si, dans le jeu « Tower Defense », un certain placement de nos tours nous permettra de survivre.

Rappel du principe de Tower Defense : un chemin est tracé sur une carte, et des ennemis avancent sur ce chemin, qui est bordé de tourelles ayant chacune une certaine portée de tir.

Dans cet exercice, nous vous fournissons une carte, comprenant un chemin, des ennemis placés à divers endroits (sur le chemin, bien entendu), ainsi que des tourelles de défense, avec leur portée de tir. Le but est d'analyser la carte et de déterminer si les tourelles sont capables d'atteindre l'ensemble de monstres présents sur la carte.

Sur la carte, on trouve les symboles suivants :


Symbole Signification


. C Une case quelconque Une case de type chemin


Explication du principe de portée d'une tourelle :

1
2
3
4
5
6
7
.......
.ooooo.
.ooooo.
.oo2oo.
.ooooo.
.ooooo.
.......

Les '.' représentent la zone hors de portée, les 'o' représentent la zone à portée, et le '2' représente la tourelle, qui a, dans ce cas, une portée de deux cases.

Une tourelle peut atteindre plusieurs ennemis dans sa portée.

ENTRÉE

  • Sur la première ligne : la hauteur de la carte ;
  • Sur la deuxième ligne : la largeur de la carte ;
  • Ensuite : la carte, comme définie précédemment.

SORTIE

  • Un entier : 1 si au moins un ennemi ne peut être atteint par une tourelle et 0 si tous les ennemis peuvent être atteints.

CONTRAINTES

N, M \<= 1000

Runtime constraints

Maximum memory usage
2048 kilobytes
Maximum execution time
1000 milliseconds

Input/output samples

Sample input
10
10
.C........
.C........
.E.2.CCCC.
.C...C..C.
.CCCCE1.C.
........C.
........C.
..ECECCCC.
.3C...4...
..C.......
Sample output
0

Submit your solution

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