Tower Defense – Épreuve régionale 2009

Niveau 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

Contraintes d'exécution

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

Exemples d'entrée/sortie

Exemple d'entrée
10
10
.C........
.C........
.E.2.CCCC.
.C...C..C.
.CCCCE1.C.
........C.
........C.
..ECECCCC.
.3C...4...
..C.......
Exemple de sortie
0