Descrição
Rafael gostava tanto de um jogo que jogava quando criança, que decidiu desenhar um mapa com as características do jogo e ver se conseguia completá-lo.
O mapa consiste de N linhas e M colunas, que divide o mapa em uma grade de N * M células. Cada uma dessas células, com exceção da célula central, contém uma seta desenhada, que indica para uma das quatro direções – Esquerda, Cima, Direita ou Baixo.
O objetivo do jogo é posicionar o personagem em alguma das células que constituem a borda do mapa, e fazer que o mesmo chegue até o centro do mapa, marcado com um X. As regras para se mover no jogo seguem a lógica das setas: O personagem só pode mover na direção que a seta aponta.
Ou seja, se o personagem está na célula [x, y] (linha x, coluna y), e nesta célula há uma seta apontada para a direita, a única célula que ele poderá alcançar dali será a célula [x, y+1], caso a mesma esteja dentro dos limites do mapa (caso não esteja, ele sairá do mapa, e perde o jogo).
Para facilitar, Rafael decidiu que ele poderia fazer K inversões de setas. Ao inverter uma seta, a mesma passa a apontar a direção oposta a qual ela apontava. Ou seja, se ela apontava para a Direita, ela apontará para a Esquerda, e vice-versa. O mesmo vale para Cima e Baixo.
Rafael agora pediu sua ajuda: É possível posicionar o personagem em alguma borda do mapa, e fazer com que ele chegue até a célula central, fazendo no máximo K inversões de setas?
Entrada
Haverá diversos casos de teste. Cada caso de teste inicia com três inteiros N, M e K (3 ≤ N, M < 100, 0 ≤ K ≤ 30, N e M são ímpares), representando, respectivamente, a quantidade de linhas e a quantidades de colunas do mapa, e o número máximo de inversões permitidas.
A seguir haverá N linhas, cada uma contendo M caracteres, que representarão o mapa que Rafael desenhou. O caractere da linha i e coluna j indica que na célula [i, j] do mapa há:
'>' – Uma seta apontando para a Direita.
'<' – Uma seta apontando para a Esquerda.
'^' – Uma seta apontando para a Cima.
'v' – Uma seta apontando para a Baixo.
'x' – A célula de destino (a qual estará sempre no centro do mapa).
O último caso de teste é identificado quando N = M = K = 0, o qual não deve ser processado.
Saída
Para cada caso de teste deverá ser impressa uma linha, contendo a palavra “Sim” caso seja possível posicionar o personagem em uma das células da borda do mapa de tal forma que ele seja guiado até a célula de destino, fazendo no máximo K inversões de setas, ou “Nao” caso contrário.
| Exemplos de Entrada | Exemplos de Saída |
|---|---|
|
5 5 0 |
Sim |
Efetue Login ou Cadastre-se para submeter uma solução.
Criado por Cristhian Bonilha | Adaptado por erich.rodriguesf |