By OBI - Olimpíada Brasileira de Informática 2014 Brazil
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:
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.
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:
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 '.').
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|