TopCoder problem "CastleGuards" used in TCHS SRM 33 (Division I Level One)



Problem Statement

    We have a rectangular castle. The first floor is protected by some number of guards. We want to have at least one guard in each row and in each column. You are given a String[] castle. The j-th character of the i-th element of castle is either '.' (free cell) or uppercase 'X' (guard). Return the smallest number of additional guards we have to place in the castle to achieve our goal.
 

Definition

    
Class:CastleGuards
Method:missing
Parameters:String[]
Returns:int
Method signature:int missing(String[] castle)
(be sure your method is public)
    
 

Constraints

-castle will contain between 1 and 50 elements, inclusive.
-Each element of castle will contain between 1 and 50 characters, inclusive.
-All elements of castle will contain the same number of characters.
-Each character of each element of castle will be either '.' or uppercase 'X'.
 

Examples

0)
    
{ "....",
  "....",
  "....",
  "...." }
Returns: 4
Here we can place 4 guards on one of the diagonals and that will satisfy us.
1)
    
{ "XX...",
  ".XX..",
  "...XX" }
Returns: 0
No additional guards needed.
2)
    
{ "....XXXX",
  "........",
  "XX.X.XX.",
  "........",
  "........" }
Returns: 3
3)
    
{ "........X..",
  "...X.......",
  "...........",
  "..X...X....",
  "...........",
  "...........",
  "........X..",
  "...........",
  "...........",
  "........X..",
  ".....X....." }
Returns: 6

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10767&pm=8017

Writer:

mateuszek

Testers:

PabloGilberto , brett1479 , Olexiy , ivan_metelsky

Problem categories:

Simple Search, Iteration