Be Wary of Roses

You’ve always been proud of your prize rose garden. However, some jealous fellow gardeners will stop at nothing to gain an edge over you. They have kidnapped, blindfolded, and handcuffed you, and dumped you right in the middle of your treasured roses! You need to get out, but you’re not sure you can do it without tram- pling any precious flowers. Fortunately, you have the layout of your garden committed to memory. It is an N × N collection of square plots (N odd), some containing roses. You are standing on a square marble plinth in the exact center. Unfortunately, you are quite disoriented, and have no idea which direction you’re facing! Thanks to the plinth, you can orient yourself facing one of North, East, South, or West, but you have no way to know which. You must come up with an escape path that tramples the fewest possible roses, no matter which direction you’re initially facing. Your path must start in the center, consist only of horizontal and vertical moves, and end by leaving the grid. Input Every case begins with N, the size of grid (1 ≤ N ≤ 21), on a line. N lines with N characters each follow, describing the garden: ‘.’ indicates a plot without any roses, ‘R’ indicates the location of a rose, and ‘P’ stands for the plinth in the center. Input will end on a case where N = 0. This case should not be processed. Output For each case, output a line containing the minimum guaranteed number of roses you can step on while escaping. Sample Input 5 .RRR. R.R.R R.P.R R.R.R .RRR. 0 Sample Output At most 2 rose(s) trampled.