Programa Pacman em C

[Bárbara Ribeiro Lunetta]

Galera, boa noite.

Estou com muita dificuldade em fazer um programa chamado PACMAN em C, gostaria da ajuda de vocês, (Lógica, Diretrizes, Programa escrito) qualquer coisa!!!

Segue as especificações:

 

Pacman é um jogo muito conhecido, onde o personagem tenta comer a maior quantidade possível de comida, 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:

1. O Pacman começa no canto superior esquerdo do tabuleiro.
2. O Pacman percorre toda a linha, da esquerda para direita, até chegar ao lado direito do tabuleiro.
3. O jogador desce uma posição, e percorre toda a linha, desta vez da direita para a esquerda.
4. 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.

Entrada

A primeira linha contém um inteiro N, o tamanho do tabuleiro do jogo, que é quadrado. Cada uma das N linhas seguintes contém N inteiros separados por um espaço em branco, que podem ser:

• 0: um espaço vazio no tabuleiro;
• 1: uma comida;
• 2: um fantasma.

Saída

Seu programa deve produzir uma única linha contendo um único inteiro, a quantidade máxima de comida que o Pacman pode levar para casa.

1 Extraído e adaptado da prova da 1ª fase da Olimpíada Brasileira de Informática, Modalidade Universitária, de 2014

Restrições

• 2 ≤ N ≤ 100
• Não há um fantasma e uma comida na mesma posição
• Não há fantasma nem comida na posição inicial do Pacman (ou seja, o primeiro número da primeira linha do tabuleiro é 0).

[isrnick]

Comece por partes, um exemplo seria primeiro lidar com o problema do caminho a ser percorrido pelo pacman:

 

Uma boa ideia sempre é desenhar/escrever representações de daquilo que se deseja fazer, assim ficará mais fácil ver qual a lógica do problema. Nesse caso desejamos saber como a matriz do tabuleiro deve ser percorrida, o que facilitará na hora de fazer a lógica do código...

 

Então vamos usar por exemplo de uma matriz 5 x 5 (ou seja, quando N = 5), nesse caso as coordenadas das posições do tabuleiro serão:

00 01 02 03 0410 11 12 13 1420 21 22 23 2430 31 32 33 3440 41 42 43 44

Segundo o enunciado o pacman deverá percorrer primeiro de 00 até 04, aí desce para 14 e percorre o caminho inverso na linha até 10, depois desce para 20 e assim por diante...

 

Vamos analisar esse comportamento separando linhas e colunas...

 

Considerando apenas as linhas o caso é simples pois o pacman sempre percorre num único sentido, de cima para baixo, logo o valor é sempre incrementado, indo de 0 a 4 (ou no caso geral de 0 até N-1).

 

Quando consideramos as colunas vemos que o sentido percorrido é invertido a cada linha, ou seja, as coordenadas das colunas vão de 0 a 4 inicialmente, mas de 4 a 0 na linha seguinte, e de 0 a 4 novamente na linha seguinte, e assim por diante. Podemos então observar que nas linhas 0, 2 e 4 as coordenadas irão de 0 a 4, enquanto nas linhas 1 e 3 elas irão de 4 a 0, e daí podemos fica fácil observar um padrão: ou seja, se a linha é par deseja-se percorrer as colunas de 0 até 4 (generalizando: 0 até N-1), e se a linhar for ímpar (= não for par) deseja-se percorrer as colunas de 4 até 0 (generalizando: N-1 até 0).

 

Logo, a lógica do caminho percorrido pelo pacman será algo do tipo:

para linhas indo de 0 até N-1:  se a linha atual for par:    para colunas indo de 0 até N-1:      <lógica de contagem de comida obtida>    fim do para  senão:    para colunas indo de N-1 até 0:      <lógica de contagem de comida obtida>    fim do para  fim do sefim do para

Agora tente aplicar algo parecido para a contagem da quantidade de comida... Monte uma tabela quadrada com 0s, 1s e 2s (vazios, comida  e fantasmas) em lugares aleatórios, a percorra e tente ver como a comida deverá ser contabilizada, e avaliar quando seria o melhor momento de parar para obter a maior quantidade de comida, e analisar qual seria o método/critério a ser avaliado pelo seu programa para tomar essa decisão. E continue com isso e veja até onde consegue chegar.

 

Se tiver problemas poste aqui o seu código e/ou dúvidas, e eu e/ou outros membros tentaremos te ajudar.