BoardPainting | Topcoder Archive

Problem Statement

There is a white rectangular board divided into a grid of unit square cells. Fox Ciel wants to paint some of the cells black, so that the board looks as described by the String[] target. More precisely: for each i, j, the cell in row i, column j of the board (0-based indices) should be painted black if target[i][j] is '#', and it should remain white if target[i][j] is '.'.

Fox Ciel paints in steps. In each step, she selects a group of white cells and paints all of them black. She is only allowed to select a contiguous sequence of white cells in a single row or in a single column.

Return the minimal number of steps needed to color the board.

Definition

Class:: BoardPainting
Method:: minimalSteps
Parameters:: String[]
Returns:: int
Method signature:: int minimalSteps(String[] target)
(be sure your method is public)

Constraints

n will be between 1 and 50, inclusive.
m will be between 1 and 50, inclusive.
target will contains exactly n elements.
Each element in target will contains exactly m characters.
Each character in target will be '#' or '.'.

Examples

```
{"#####"}
```
```
Returns: 1
```
Fox Ciel can select the entire row of the board and paint it all black in a single step.
```
{"#####",
 ".....",
 "#####",
 ".....",
 "#####"}
```
```
Returns: 3
```
In each turn, Ciel selects and colors one of the rows that should be black.
```
{"..#..",
 "..#..",
 "#####",
 "..#..",
 "..#.."}
```
```
Returns: 3
```
Note that each sequence of cells selected by Ciel has to be a contiguous sequence of white cells. It is not allowed to select a black cell. Therefore the best solution has three steps. One possibility: first she selects row 2, then the first two cells in column 2, and finally the last two cells in column 2.

{"#####",
 "..#..",
 "#####",
 "..#..",
 "#####"}

Returns: 5

{".#.#.",
 "#####",
 ".#.#.",
 "#####",
 ".#.#."}

Returns: 8

{".##.####.####.#########.##..",
 "##.#.####################.##",
 ".##.###.##.###.###.###.###..",
 "#..###..#########..###.##.##",
 "####..#######.#.#####.######",
 "##.######.#..#.#############",
 "##.######.###########.######",
 "#######.#######.#..###.#.###",
 "#####..#######.#####.#.###.#",
 "#..#################.#.####.",
 "##.######..#.#####.######.##",
 "..#.#############.#.##....#.",
 "....##..##..#.#####.#.###.##",
 "##.#########...#..#.#.######",
 "##.#..###########..#..####.#",
 "#.####.###.########.########",
 "#####.#########.##.##.######",
 ".##.####..###.###...######.#"}

Returns: 88

```
{"...................."}
```
```
Returns: 0
```
Note that the target can be totally white.

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.