TopCoder problem "TurnOnTheLights" used in TCHS SRM 60 (Division I Level Two)



Problem Statement

    

Milena is in a rectangular room with a floor divided into equal square cells. A cell is considered good if it contains a light bulb and bad if it does not. The j-th character of the i-th element of the String[] floor is uppercase 'Y' if the cell at row i, column j is good and 'N' if it is bad. At time 0, Milena is at cell (row, col) and all the light bulbs are turned off. Cell (row, col) will always be a bad cell. All row and column indices are 0-based.

Milena will choose one direction (up, down, left or right) and move at most K cells in that direction. She is not allowed to leave the room. When she steps on a good cell, the light bulb in that cell will turn on, and the light bulbs in all its neighboring good cells will also turn on. Two cells neighbor each other only if they share a side. Return the maximal number of light bulbs Milena can turn on.

 

Definition

    
Class:TurnOnTheLights
Method:countLights
Parameters:String[], int, int, int
Returns:int
Method signature:int countLights(String[] floor, int K, int row, int col)
(be sure your method is public)
    
 

Constraints

-floor will contain between 1 and 50 elements, inclusive.
-Each element of floor will contain between 1 and 50 characters, inclusive.
-All elements of floor will be of the same length.
-Each character of each element of floor will be an uppercase 'Y' or an uppercase 'N'.
-K will be between 1 and 50, inclusive.
-row will be between 0 and (number of elements in floor)-1, inclusive.
-col will be between 0 and (number of characters in the first element of floor)-1, inclusive.
-Character col of element row of floor will be an uppercase 'N'.
 

Examples

0)
    
{"N"}
50
0
0
Returns: 0
In this case Milena can't make any steps. Note that Milena doesn't have to make exactly K steps, so making no steps is valid.
1)
    
{"YNNYYYY",
 "YNYNYYY",
 "NYYYYYN",
 "YYNYYYY"}
4
1
1
Returns: 9
Choosing to make 4 steps to the right will allow us to turn on 9 light bulbs. The diagrams below show the configuration of the room after each step ('+' represents a light bulb that is turned on): 
YNNYYYY     YNNYYYY     YNNYYYY     YNNY+YY     YNNY++Y
YNYNYYY --> YN+NYYY --> YN+NYYY --> YN+N++Y --> YN+N+++
NYYYYYN     NY+YYYN     NY+YYYN     NY+Y+YN     NY+Y++N 
YYNYYYY     YYNYYYY     YYNYYYY     YYNYYYY     YYNYYYY
2)
    
{"NNNNY",
 "NNNNN",
 "NNNNN"}
2
1
2
Returns: 0
Milena can't step on a good cell, so it doesn't matter which direction to choose.
3)
    
{"YNYNY",
 "NYNYY",
 "NNNNN"}
1
2
4
Returns: 3
Here it's best to make one step up.
4)
    
{"NNNYNN",
 "NNNNNN",
 "YNYNNN",
 "YYYYYY",
 "YYNYNY",
 "NNYYYN",
 "YYYYYY"}
5
2
3
Returns: 10
5)
    
{"YYYYY",
 "YYYYY",
 "YYYYN",
 "YYYYY",
 "YYYYY"}
4
2
4
Returns: 12

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13529&pm=9864

Writer:

boba5551

Testers:

PabloGilberto , Olexiy , ivan_metelsky

Problem categories:

Brute Force, Simple Search, Iteration