By Paola Salvador, PUCRS Brazil
Alice moved to a city that is known for its many castles, she is exploring the town and wants to visit as many as possible castles. In order to this adventure become real, Alice created some rules, the visiting can start at any castle (C) of the town, although she cannot cross any river after she alredy started visiting, even that the river is under a bridge (P). Also, Alice's rule does not consider diagonals movements, so she can only move north, south, east or west. You must help Alice find out the max quantity of castles she will be able to visit.
First line contains two integers (H ≤ 400 and L ≤ 400), that represent height (H) and width (L) of the city and the following lines contain the city map, where C represents a castle area, P an bridge and R a river separated by spaces. Each test case ends with a blank line.
An integer that represents the max visits Alice can make in one day.
Input Sample | Output Sample |
5 5 |
5 |