TopCoder problem "CrossWord" used in SRM 174 (Division II Level One)



Problem Statement

    

You are in the process of creating a crossword puzzle. You've already designed the board, but now you need to come up with words of various sizes to put in the puzzle. An empty crossword puzzle consists of filled squares ('X') and empty squares ('.'). Here is an example of a board with 5 rows and 6 columns:

X....X

X.XX.X

...X..

X.XX.X

..X...

A "slot" of length N is defined as exactly N empty squares in a row, surrounded on either side by either a filled square or the edge of the board. N must be at least 2. There are five horizontal slots in the example puzzle above:

  1. First row, length = 4
  2. Third row, length = 3
  3. Third row, length = 2
  4. Fifth row, length = 2
  5. Fifth row, length = 3

Given a String[] board, representing an empty crossword puzzle, and an int size, your method should return the number of horizontal slots in the puzzle that are exactly size characters in length. Each element of board represents one row of the puzzle.

 

Definition

    
Class:CrossWord
Method:countWords
Parameters:String[], int
Returns:int
Method signature:int countWords(String[] board, int size)
(be sure your method is public)
    
 

Constraints

-board will contain between 3 and 50 elements, inclusive.
-Each element of board will contain between 3 and 50 characters, inclusive.
-Each element of board will be the same length.
-board will consist of only '.' and 'X' characters, and will contain at least two '.' characters.
-All '.' characters in board will be connected horizontally or vertically.
-size will be between 2 and 50, inclusive.
 

Examples

0)
    
{"X....X",
 "X.XX.X",
 "...X..",
 "X.XX.X",
 "..X..."}
3
Returns: 2

The example from above. Note that there are two horizontal slots with length = 3.

1)
    
{"...X...",
 ".X...X.",
 "..X.X..",
 "X..X..X",
 "..X.X..",
 ".X...X.",
 "...X..."}
3
Returns: 6

There are two slots of length 3 on both the first and seventh rows, and one slot each on the second and sixth rows, for a total of 6.

2)
    
{".....X....X....",
 ".....X....X....",
 "..........X....",
 "....X....X.....",
 "...X....X....XX",
 "XXX...X....X...",
 ".....X....X....",
 ".......X.......",
 "....X....X.....",
 "...X....X...XXX",
 "XX....X....X...",
 ".....X....X....",
 "....X..........",
 "....X....X.....",
 "....X....X....."}

5
Returns: 8
3)
    
{"...",
 "...",
 "..."}
50
Returns: 0
4)
    
{"....",
 "....",
 "...."}
3
Returns: 0

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4675&pm=2232

Writer:

LunaticFringe

Testers:

lbackstrom , brett1479

Problem categories:

String Manipulation