Vacuum Cleaner Robot
By Flávio Zavan, UFPR 
Brazil
By Flávio Zavan, UFPR Brazil
Ricciardi, the vacuum cleaner robot, received orders. It must clean the maximum possible number of the N dusts on the ground and reach the recharge station. It seems to be a trivial task. However, Ricciardi’s battery is damaged, and it can make only M moves before it exhausts.
The robot is located in a rectangular room with W × H square cells. In one move, it can go to the cell directly above, below, to the left or to the right of its current cell, but only if it does not contain any obstacle. Determined to save energy while finishing its job, Ricciardi asked you to write a program that calculates the maximum number of dusts it can clean.
The input contains several test cases. The first line of each test case contains two integers N (1 ≤ N ≤ 8) and M (1 ≤ M ≤ 109). The second line contains two integers W and H (5 ≤ W, H ≤ 100).
The following H lines contains W characters each, describing the room. Obstacles are represented by '#', empty cells by '.' , Ricciardi’s initial cell by 'R', dusts by '*' and the recharge station by 'S'.
Riccardi automatically cleans a dust when passing by it. It can also pass over the recharge station, the same way it can pass over any empty cell.
The input ends with end-of-file (EOF).
For each test case, print a single line with one integer only, the maximum number of dusts the robot can collect before going to the recharge station. If the robot cannot reach the station, print -1.
| Input Sample | Output Sample |
|
3 10 |
1 |