Pouvez-vous rester sur la grille ?
Lorsque vous concevez un jeu vidéo, vous travaillez sur une grille de dimensions
h par w. Dans chaque case, une direction (<>v^) indique où vous devez vous déplacer si vous apparaissez sur cette case.Vous commencez depuis une case choisie au hasard, puis vous vous déplacez dans la direction indiquée. Dans certains cas, il est possible de sortir de la grille, ce qui met immédiatement fin à la partie.
> | > | v | > | > |
^ | < | < | v | < |
v | ^ | ^ | < | > |
< | v | ^ | > | < |
En tant que concepteur du jeu, vous désirez éviter qu’il y ait trop de cases menant à une sortie de la grille. Vous souhaitez donc calculer le nombre de cases à partir desquelles on reste toujours à l’intérieur de la grille.
Entrée
La première ligne de l’entrée contient deux entiers
h et w (1 ≤ h, w ≤ 1000).Les
h lignes suivantes contiennent chacune w caractères, indiquant la direction à suivre (<>v^) lorsque l’on se trouve sur cette case.Sortie
Le programme doit afficher le nombre de cases à partir desquelles on ne quitte jamais la grille.
Exemples
Entrée | Sortie |
4 5
>>v>>
^<<v<
v^^<>
<v^>< | 14 |
Explication
> | > | v | > | > |
^ | < | < | v | < |
v | ^ | ^ | < | > |
< | v | ^ | > | < |
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB