Consegues manter-te na grelha?
Ao conceberes um jogo de computador, estás a trabalhar numa grelha de dimensões h-por-w. Em cada célula, existe uma direção (<>v^) que indica para onde deves mover-te caso comeces nessa célula.
Começas numa célula aleatória e segues a direção indicada. Em alguns casos, podes sair da grelha, o que termina o jogo.
> | > | v | > | > |
^ | < | < | v | < |
v | ^ | ^ | < | > |
< | v | ^ | > | < |
Como és o(a) designer do jogo, pretendes garantir que não haja muitas destas células problemáticas. Por isso, queres calcular quantas células existem a partir das quais consegues permanecer sempre dentro da grelha.
Entrada
A primeira linha da entrada contém dois inteiros h e w (1 ≤ h, w ≤ 1000).
As seguintes h linhas contêm w caracteres que representam a direção para onde te deves mover ao começares nessa célula (<>v^).
Saída
O programa deve imprimir o número de células a partir das quais nunca sais da grelha.
Exemplos
Entrada | Saída |
|---|---|
4 5 | 14 |
Explicação
> | > | v | > | > |
^ | < | < | v | < |
v | ^ | ^ | < | > |
< | v | ^ | > | < |
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB