Prologin
2025
Énoncé¶
Lors du siège de Troie, Agamemnon réfléchissait un soir dans sa tente sur la stratégie à appliquer pour prendre la cité. Avant d'atteindre les remparts, il lui faudrait se battre sur le champ de bataille, et pour cela il souhaiterait envisager les mouvements possibles de son armée. Il matérialise alors la plaine devant la cité par un plateau de jeu carré sur une grande table, et dispose ses unités militaires à diverses positions. Il souhaite savoir combien de mouvements sont possibles.
On considère qu'une unité d'infanterie peut se déplacer d'une case dans toutes les directions (diagonales comprises), une unité de cavalerie de deux cases dans toutes les directions, et une unité de trébuchet d'une case en avant (vers le haut du plateau) ou en arrière (vers le bas du plateau).
On représente une unité d'infanterie par la lettre I, une unité de cavalerie par
la lettre C, et une unité de trébuchet par la lettre T.
Attention, Agamemnon ne tolérera pas que son armée rebrousse chemin ou se laisse repousser. Il ne validera donc aucun mouvement faisant sortir une de ses unités de la plaine (donc du plateau de jeu !).
Une unité ne peut évidemment pas se déplacer là où une unité est déjà présente,
mais peut "traverser" une autre unité pour se déplacer. Par exemple, un
cavalier peut très bien traverser une unité adjacente pour accéder à un
emplacement à une distance de deux. Une unité ne peut pas non plus se déplacer
sur une case inaccessible, représentée par la lettre x.
Un emplacement vide est représenté par un point (.).
Entrée¶
L’entrée contiendra :
- Sur la première ligne, un entier : dim, la dimension de la matrice carrée représentant le terrain.
- Sur les lignes suivantes, une liste de dim éléments : terrain, la
représentation du terrain sur lequel peuvent se déplacer les unités.
- Une ligne par élément de la liste : une liste de dim caractères juxtaposés.
Sortie¶
Un nombre entier représentant le nombre de déplacements possibles.
Contraintes¶
- $1 \le \text{dim} \le 100$