TopCoder problem "ProgrammingRobots" used in TCHS SRM 61 (Division I Level Three)



Problem Statement

    You are given a String[] maze, where the j-th character of the i-th element describes the cell at row i, column j. '#' denotes a wall, '.' denotes an empty space, and 'R' denotes an empty space where you have the option of placing a single robot at time 0. The maze is surrounded on all four sides by walls.

Each robot in the maze executes the same program starting at time 0. The program consists of a sequence of commands, where each command is one of the four cardinal directions (up, down, left or right). When a robot executes a command, it attempts to move one cell in the direction specified by the command. If the destination cell is a wall, the robot will not move. Multiple robots are allowed to occupy the same cell at the same time. Each command takes exactly 1 second regardless of whether or not the robot moves.

Your goal is to write a program that will enable to you place as many robots as possible into 'R' cells such that all of them will end up in the same cell when the program finishes. Return this maximum possible number of robots.
 

Definition

    
Class:ProgrammingRobots
Method:numberOfRobots
Parameters:String[]
Returns:int
Method signature:int numberOfRobots(String[] maze)
(be sure your method is public)
    
 

Constraints

-maze will contain between 1 and 50 elements, inclusive.

-Each element of maze will contain between 1 and 50 characters, inclusive.

-Each character in maze will be '#', '.' or 'R'.

-Each element of maze will contain the same number of characters.

 

Examples

0)
    
{"#R##",
 "##.#",
 "##.#",
 "..R."}
Returns: 1
You cannot place robots in both 'R' cells because they won't be able to reach each other.
1)
    
{"....",
 "...R",
 ".RR."}
Returns: 3
Place a robot in every 'R' cell. One possible program that will move them all to the same cell is: down, right, right.
2)
    
{"####..R.##",
 "#.#.####.#",
 "..R....RR#",
 "#.#.R..#..",
 "#.R#.R.#.#",
 "###RR##...",
 "########.#",
 "#######..R"}
Returns: 9

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10173

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13530&pm=10173

Writer:

Gluk

Testers:

PabloGilberto , Olexiy , ivan_metelsky

Problem categories:

Search