URI (BEECROWD) - 2451 - PacMan - Ad-Hoc - C e C++

Vamos a mais uma solução por aqui!? Dessa vez o problema "PacMan", da categoria Ad-hoc. É um problema que vale poucos pontos, mas que apresenta uma solução interessante por manipular strings. Vamos ver como se resolve, na sequência desse post.

Plataforma: Beecrowd (antiga URI)

Problema: 2451

Enunciado:

Pacman é um jogo muito conhecido, onde o personagem tenta comer a maior quantidade possível de bolinhas, tendo ao mesmo tempo que fugir de vários fantasmas. Dessa vez, nosso personagem quer carregar a comida coletada para casa, mas o encontro com um fantasma, ao invés de terminar o jogo, faz com que toda a comida coletada seja roubada.

Neste problema os fantasmas não se movem, e o jogador sempre faz o Pacman percorrer o seguinte caminho:

O Pacman começa no canto superior esquerdo do tabuleiro.

O Pacman percorre toda a linha, da esquerda para direita, até chegar ao lado direito do tabuleiro.

O jogador desce uma posição, e percorre toda a linha, desta vez da direita para a esquerda.

As etapas 2 e 3 se repetem até que todo o tabuleiro tenha sido percorrido.

Infelizmente, Pacman não pode ignorar os comandos do usuário para fugir dos fantasmas ou pegar mais comida, mas ele pode, a qualquer momento, se aproveitar de um bug de implementação e interromper o jogo, levando consigo toda a comida que estiver carregando.

Você deve escrever um programa que determine a maior quantidade de comida que o Pacman pode levar, se escolher a melhor hora possível para sair. Note que o jogador também tem a opção de não sair antes do final do jogo.

Linguagens: C e C++

Solução:

Nesta solução, a proposta foi basicamente ler todas as linhas na ordem natural. Para isso, as linhas ímpares (considerando que se começa em uma linha par -- zero) foram invertidas. Isso facilita a busca para depois não precisar calcular os índices de forma diferente entre linhas pares e ímpares. Assim, basta percorrer o tabuleiro do jogo normalmente, na ordem natural, e procurar pelas maiores sequências de "o" até que um "A" seja encontrado. A maior sequência deve ser sempre armazenada (max) e comparada com a sequência atual (variável "atual"), que, se for maior, é atribuída à variável max também, bem como é zerada após esta ação para que se comece uma nova sequência a partir da posição atual no tabuleiro.

As soluções em C e C++ seguem a mesma lógica, mas você pode analisar as funções de reversão de string, que são diferentes. Em C++ eu aproveitei uma função já existente, reverse(). Em C eu mesmo implementei, para dar um toque especial e diferenciar as soluções .:)

Código em C++:

#include <algorithm>
#include <iostream>
#include <string>

using namespace std;

int main () {
   int n, max = 0, atual = 0;
   string str;
   cin >> n;

   for (int i = 0; i < n; i++) {
      cin >> str;
      if (i & 1)
         reverse(str.begin(), str.end()); 

      for (int j = 0; j < n; j++) {
         if (str.at(j) == 'A') {
            if (atual > max)
               max = atual;
            atual = 0;
         }
         else if (str.at(j) == 'o')
            atual++;
      }
   }
   if (atual > max)
      cout << atual << endl;
   else
      cout << max << endl;

   return 0;
}

Código em C:

#include <stdio.h>

void reverteString (char *str, int n) {
    int i, temp;
    for (i = 0; i < n / 2; i++) {  
        temp = str[i];  
        str[i] = str[n - i - 1];  
        str[n - i - 1] = temp;  
    }  
}  

int main () {
   int n, max = 0, atual = 0, i, j;
   scanf("%d", &n);
   char str[n+1];
   for (i = 0; i < n; i++) {
      scanf("%s", str);
      if (i & 1)
         reverteString(str, n);
      for (j = 0; j < n; j++) {
         if (str[j] == 'A') {
            if (atual > max)
	       max = atual;
            atual = 0;
	 }
	 else if (str[j] == 'o')
         atual++;
      }
   }
   if (atual > max)
      printf("%d\n", atual);
   else
      printf("%d\n", max);

   return 0;

}

Novamente, segue os dados para apoio:

Chave aleatória (PIX) para doações: 6d8bc7a8-5d74-493a-ab7a-3515baf35956

Ajude-nos a manter o blog!