Entraînement › Demi-finale 2009, épreuve machine › Tower Defense

Demi-finale 2009, épreuve machine - Tower Defense

DIFFICULTE

LIMITE DE MEMOIRE

2048 ko

LIMITE DE TEMPS

1000 ms

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
. Une case quelconque
C Une case de type chemin
E Une case de type ennemi
0 à 9 Une tourelle, dont la portée est définie par le chiffre indiqué

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

.......
.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

EXEMPLE(S) D'ENTREE/SORTIE

Exemple 1
en entrée ...

10
10
.C........
.C........
.E.2.CCCC.
.C...C..C.
.CCCCE1.C.
........C.
........C.
..ECECCCC.
.3C...4...
..C.......
en sortie ...
0