CastleGuards | Topcoder Archive

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

```
{ "....",
  "....",
  "....",
  "...." }
```
```
Returns: 4
```
Here we can place 4 guards on one of the diagonals and that will satisfy us.

{ "XX...",
  ".XX..",
  "...XX" }

Returns: 0

No additional guards needed.

{ "....XXXX",
  "........",
  "XX.X.XX.",
  "........",
  "........" }

Returns: 3

{ "........X..",
  "...X.......",
  "...........",
  "..X...X....",
  "...........",
  "...........",
  "........X..",
  "...........",
  "...........",
  "........X..",
  ".....X....." }

Returns: 6

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.