Solução Informática - Nível Intermediário - Semana 17

Solução por Anita Ramos

Esse é um típico problema de olimpíada que exige mais o pensamento lógico e o estabelecimento de uma estratégia do que necessariamente comandos mais complexos e avançados. A solução a seguir segue essa ideia de que uma boa lógica pode resolver o problema.

A ideia consiste em armazenar os caracteres em uma matriz de char e posteriormente percorrer esse tabuleiro (matriz) de acordo com a paridade de cada linha. Assim, em linhas ímpares se lê da esquerda para a direita e em linhas pares se lê da direita para a esquerda. Durante essa análise, se o caractere for o, ele soma 1 à cont e se for A, ele zera a variável cont. Por fim, ele calcula o máximo entre a resposta anterior, res, e a variável cont.

Apenas como observação, os comandos utilizados variam entre for(), if/else, scanf(), printf(), entre outros, considerados mais básicos, reforçando a simplicidade do código.

Segue o código comentado para melhor compreensão da solução:


#include<bits/stdc++.h> //biblioteca utilizada
using namespace std;
const int MAXN=110; //declaração do valor de 'MAXN'
char v[MAXN][MAXN]; //declaração de uma matriz de char
int main()
{
int N,cont=0,res=0; //declaração das variáveis
scanf("%d\n", &N); //lê o valor de 'N'
for(int i=1; i<=N; i++) //1º loop para ler os caracteres
for(int j=1; j<=N; j++) //2º loop para ler os caracteres
{
scanf(" %c", &v[i][j]); //lê um caractere
}
for(int i=1; i<=N; i++) //loop para percorrer todas as linhas do tabuleiro
{
if(i%2==0) //se a linha é par
{
for(int j=N; j>=1; j--) //percorre a linha de trás para frente
{
if(v[i][j]=='o')cont++; //se for comida, soma-se 1 a 'cont'
if(v[i][j]=='A')cont=0; //se for um fantasma, 'cont' zera
res=max(res,cont); //'res' assume o valor máximo entre ela mesma e 'cont'
}
}
else //se a linha é ímpar
{
for(int j=1; j<=N; j++) //percorre a linha do início ao final
{
if(v[i][j]=='o')cont++; //se for comida, soma-se 1 a 'cont'
if(v[i][j]=='A')cont=0; //se for um fantasma, 'cont' zera
res=max(res,cont); //'res' assume o valor máximo entre ela mesma e 'cont'
}
}
}
printf("%d", res); //imprime a resposta
return 0; // retorna a 0
}

view raw

Pac-man.cpp

hosted with ❤ by GitHub