Matrizes, Arquivo etc

[matas]

Me ajudem por favor, pelo menos na lógica ou qualquer linguagem, qualquer coisa que puderem me ajuda, mesmo se estiver errado.

Tele-entrega em Manhattan

Arquivo fonte: tele.c, tele.cc, tele.cpp ou tele.pas

O professor Orlando Teodoro Vite descobriu uma mina de dinheiro agregando seus conhecimentos

de informática com o ramo de tele-entrega. Ele se mudou para Manhattan e, com um grupo de

alunos, montou a empresa ArBlu, revolucionando e agilizando os serviços de tele-entrega. O filão

encontrado foi que os entregadores tradicionais desperdiçam muito tempo estudando o percurso a

ser realizado e freqüentemente se perdem.

Na ArBlu, os motoboys recebem o roteiro das entregas na forma de uma cadeia de caracteres

(string), a ser fixada no volante da moto, indicando o trajeto a ser seguido. Esta técnica funciona

porque em Manhattam todas as quadras possuem formato e orientação uniforme (retangular).

A cadeia de caracteres obedece à seguinte codificação:

· “n” significa andar uma quadra para o norte;

· “s” significa andar uma quadra para o sul;

· “l” significa andar uma quadra para o leste;

· “o” significa andar uma quadra para o oeste;

Por exemplo, se a cadeia fosse “lnlnooosls” , o caminho percorrido seria o mostrado na figura

abaixo.

N

S

O

L

ArBlu

1. Tarefa

Escrever um programa que valide cada trajeto a ser realizado pelo motoboy, ou seja, deve-se

verificar se o trajeto volta ao ponto de origem e se o trajeto encontra-se dentro dos limites da

cidade. Manhattan possui formato retangular e, relativamente à sede da empresa ArBlu, tem 5

quadras ao norte, 4 quadras ao sul, 10 quadras ao leste, e 16 quadras ao oeste.

2. Entrada

A entrada é composta de vários roteiros completos, representados cada qual por uma cadeia de

caracteres. A primeira linha da entrada contém um número inteiro n que corresponde ao número

rotas que devem ser testadas. Cada uma das n linhas seguintes contém uma rota.

Exemplo de Entrada

4

lnonllsssoon

nnlnooss

nossoslsslslnnnlnnoo

nlnnnllsslnnlssssooooo

3. Saída

Para cada roteiro de entrada, seu programa deve indicar se é válido, ou seja, se volta à origem e se

está dentro dos limites da cidade. Se estas duas condições forem satisfeitas o programa deve gerar

como saída “OK”, caso alguma condição não seja satisfeita, deve gerar como saída “NOK” .

Exemplo de Saída

OK

NOK

NOK

OK

(esta saída corresponde ao exemplo de entrada acima)

4. Restrições

0 <= n <=10.000

0 < tamanho da cadeia de caracteres que define uma rota < 100

[Mnemonic]

Você pode representar as quadras usando uma matriz:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 X 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

o X representa o seu ponto de partida [5][17] numa matriz 10x27.

Digamos que todas as posições estejam preenchidas com 0, menos a posição 5x17, que é 1.

Se a entrada for NLLSOO você testa cada caractere da entrada e:

N: matriz[x-1][y] (uma linha pra cima)

S: matriz[x+1][y] (uma linha pra baixo)

L: matriz[x][y+1] (uma coluna pra direita)

O: matriz[x][y-1] (uma coluna pra esquerda)

Enquanto caminha pela matriz, você vai fazendo os testes pra ver o valor das linhas está entre 0-9 e as colunas entre 0-26 (os limites da cidade). Assim como testa se no final voltou pro ponto de origem.

[matas]

Humm entendii muito obrigado!