Algorithm
Problem Name: 2 AD-HOC - beecrowd | 2451
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2451
PacMan
By OBI - Olimpíada Brasileira de Informática 2014 
Brazil
Timelimit: 1
Pac Man is a popular game where the character tries to eat as much as possible balls, whilst having to flee several ghosts. This time our character wants to carry the food collected home, but the encounter with a ghost, instead of finishing the game, makes all the food collected is stolen.
In this problem the ghosts do not move, and the player always makes the Pacman go through the following path:
- The Pacman begins in the upper left corner of the board.
- The Pacman runs the line, from left to right, until you reach the right side of the board.
- The player down one position, and runs the line, this time from right to left.
- Steps 2 and 3 are repeated until the entire board has been gone through.
Unfortunately, Pacman can not ignore the user's commands to escape the ghosts or get more food, but it can, at any time, take advantage of an implementation bug and stop the game, taking all the food you are loading.
You should write a program to determine the largest amount of food the Pacman can take, if you choose the best possible time to leave. Note that the player also has the option to not leave before the end of the game.
Input
The first line contains an integer N (2 ≤ N ≤ 100), the game board size, which is square. Each of the following N lines contains N characters, which can be:
- '.' Empty space;
- 'o' a meal;
- 'A' a ghost.
There is not a ghost and a meal in the same position.
There is no ghost or food in the initial position (the first character of the first line of the board is '.').
Output
Your program should produce a single line containing a single integer, the maximum amount of food that the Pacman can take home.
| Input Sample | Output Sample |
|
5 .ooo. ..ooA ..Aoo Aoooo ..ooo |
6 |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <algorithm>
#include <cstdio>
using namespace std;
#define MAXN 200
char matriz[MAXN][MAXN];
int soma, resposta, n, i, j;
int main() {
scanf("%d", &n);
for (i = 0; i < n; i++) scanf("%s", matriz[i]);
for (i = 0; i < n; i++) {
if (i % 2 == 0) {
for (j = 0; j < n; j++) {
if (matriz[i][j] == 'o') soma++;
if (matriz[i][j] == 'A') soma = 0;
resposta = max(resposta, soma);
}
} else {
for (j = n - 1; j >= 0; j--) {
if (matriz[i][j] == 'o') soma++;
if (matriz[i][j] == 'A') soma = 0;
resposta = max(resposta, soma);
}
}
}
printf("%d\n", resposta);
return 0;
}
Input
Output