XXVI Olimpíada Brasileira de Informática
Submeta sua solução

Nome do arquivo: setas.x, onde x deve ser c, cpp, java, js ou py

Setas

Gabriel é um garoto que gosta muito de um jogo onde há várias letras em um tabuleiro e o jogador precisa rapidamente pisar nas letras corretas, de acordo com as instruções na tela, seguindo uma música. Cansado de vencer, Gabriel inventou um novo jogo: agora temos um tabuleiro quadrado, com N células de cada lado, em que cada célula possui uma seta que aponta para uma das quatro posições vizinhas. O jogador primeiro escolhe uma célula inicial para se posicionar e, quando a música começa, ele deve caminhar na direção para onde a seta em que ele está aponta. Ganha o jogo quem pisar em mais setas corretas durante um período de tempo.

O problema é que Gabriel joga tão rápido que quando a seta atual manda ele sair do tabuleiro, ele segue a orientação, muitas vezes quebrando alguns objetos próximos. Quando isso acontece, dizemos que a célula inicial deste jogo não é segura, pois leva a um caminho que termina fora do tabuleiro. A figura abaixo mostra dois tabuleiros.

Ajude Gabriel: dada a configuração do tabuleiro, determine quantas células são seguras para ele iniciar o jogo.

Entrada

A primeira linha da entrada contém um inteiro N, o tamanho do tabuleiro. Cada uma das N linhas seguintes contém N caracteres, com as direções das setas. As direções válidas são:
  • "V" Aponta para a célula da linha abaixo, na mesma coluna
  • "<" (sinal menor-que) aponta para a célula à esquerda, na mesma linha
  • ">" (sinal maior-que) aponta para a célula à direita, na mesma linha
  • "A" Aponta para a célula da linha acima, na mesma coluna

Saída

Seu programa deve produzir um único inteiro, o número de células seguras.

Restrições

  • 1 ≤ N ≤ 500

Informações sobre a pontuação

  • Em um subconjunto dos casos totalizando 50 pontos, 1 ≤ N ≤ 50.

Exemplos

Entrada
3
>>V
AV<
A<>
Saída
8
	
Entrada
4
>>V<
A<<<
AAA>
>>>A
Saída
11
	
Tarefas Programação Nível 1
Promoção
logo sbc
Patrocínio
Apoio
Coordenação