domingo, 31 de maio de 2015

19948. PacMan

Olá meus amigos nerds. Hoje vamos brincar de Pacman, já que é isso que o problema 19948. PacMan nos pede para fazer. Mais especificamente, dadas as posições do pacman, comida e fantasmas determinar quantos pontos o pacman consegue fazer.

Solução


Vou confessar que não resisti a tentação de escrever sobre um problema com esse nome, mesmo que ele seja muito fácil (o que obviamente eu só descobri após o ler :P). Basta iterar sobre a matriz que representa o campo de jogo e contar quantos pontos o jogador faria usando a estratégia descrita no problema. É só zerar os pontos se ele encontrar um fantasma, e imprimir no final a maior quantidade de pontos que ele fez.

Implementação




quinta-feira, 28 de maio de 2015

2609. Trilhas

Olá meus amigos nerds. Hoje vamos brincar fazer trilhas, já que é isso que o problema 2609. Trilhas nos pede para fazer. Mais especificamente, dadas as informações sobre distâncias e altitudes de um conjunto de trilhas, determinar qual é a trilha que exige o menor esforço de subida. Onde o esforço de subida é proporcional ao desnível do trecho percorrido.

Solução


O problema não nos diz como calcular o esforço de subida, mas apenas que ele é proporcional ao desnível do trecho, em outras palavras à altura do trecho subido. Ora mas se o esforço é proporcional a cada uma das alturas ele será proporcional a soma delas. Sendo assim, o problema fica bem fácil, basta calcular a soma das alturas. Para isso, é só percorrer o vetor com a altura dos trechos e ir fazendo as diferenças entre dois trechos seguidos.

Um detalhe importante é que ele não se importa com o sentido do trecho, assim sendo devemos calcular o desnível do terreno considerando que ele pode estar indo do trecho a para o b, ou vice versa.

A resposta final será a opção de trilha com a menor soma das alturas.

Implementação




terça-feira, 26 de maio de 2015

11006. Colorindo

Olá meus amigos nerds. Dizem que livrinhos de colorir estão na moda hoje em dia. Se isso é verdade eu não sei, mas sei que hoje vamos brincar de colorir alguns, já que é isso que o problema 11006. Colorindo nos pede para fazer. Mais especificamente, dados um desenho quadriculado e um ponto que se deseja começar a colorir, devemos determinar quantos quadrados desse desenho serão coloridos no total sendo que se eu colorir um quadrado devo colorir todos os seus vizinhos a menos que eles já estejam coloridos.

Solução


Esse é um problema bem simples. O processo de colorir descrito no problema é exatamente uma busca em largura, feita sobre o papel quadriculado. Sendo assim basta executarmos a busca e contarmos quantos quadradinhos serão coloridos ao final do processo.

Implementação




Lembram que no problema anterior eu preenchi as bordas da matriz com 0's. Vejam que nesse problema, como eu não fiz isso a cada iteração do loop eu tenho que ficar checando se x e y estão de fato dentro da matriz.

quarta-feira, 20 de maio de 2015

18538. Robô

Olá meus amigos nerds. Hoje vamos determinar onde um robô de limpeza deve parar depois de limpar um salão. Meio chato, mas nem só de coisas legais vive o mundo, né! Já que é isso que o problema 18538. Robô nos pede para fazer. Mais especificamente, dados um mapa indicando a cor de cada ladrilho no chão e a posição inicial do robô, devemos determinar a posição final do robô que só se locomove através de ladrilhos pretos.

Solução


Esse é um problema bem simples. Basta simularmos a trajetória do robô. Para isso, basta ir iterando sobre a posição atual do robô procurando pela próxima posição válida. Para não correr o risco de voltar pelo mesmo caminho que o robô veio, basta ir apagando o caminho a medida que ele vai sendo percorrido.

Implementação




Observe como envolvo a minha matriz com 0's (sentinelas) para evitar que a busca saia dos limites da matriz e eu tenha que ficar verificando isso no código.