Connection Status:
Competition Arena > BoardPainting

BoardPainting

SRM 577 · 2012-12-13 · by cgy4ever

SRM 577 · 2012-12-13 · by cgy4ever · Graph Theory, Math
Class Name: BoardPainting
Return Type: int
Method Name: minimalSteps
Arg Types: (vector<string>)
Problem Statement

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.

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
0)
{"#####"}
Returns: 1

Fox Ciel can select the entire row of the board and paint it all black in a single step.

1)
{"#####",
 ".....",
 "#####",
 ".....",
 "#####"}
Returns: 3

In each turn, Ciel selects and colors one of the rows that should be black.

2)
{"..#..",
 "..#..",
 "#####",
 "..#..",
 "..#.."}
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.

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

Note that the target can be totally white.

Submissions are judged against all 127 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class BoardPainting with a public method int minimalSteps(vector<string> target) · 127 test cases · 2 s / 256 MB per case

Submitting as anonymous