back to the menu

Flag Counter TopCoder SRM 577 - 1000: BoardPainting

SRM 577 1 1000 BoardPainting


Problem Statement

一个n*n的画板上有若干个格子需要染色,
每次可以选择一个起点然后沿着上下左右任意一个方向染色,
每次染色不能经过不需要染色或者已经染过色的格子,
染色过程中也不能改变方向,求最小化染色次数。
数据保证n <= 50。

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

(be sure your method is public)

Limits

Constraints

Test cases

  1. input
    • target { "#####" }
    output
    Returns 1
    note
    Fox Ciel can select the entire row of the board and paint it all black in a single step.
  2. input
    • target {"#####",
       ".....",
       "#####",
       ".....",
       "#####"}
    output
    Returns 3
    note
    In each turn, Ciel selects and colors one of the rows that should be black.
  3. input
    • target {"..#..",
       "..#..",
       "#####",
       "..#..",
       "..#.."}
    output
    Returns 3
    note
    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.
  4. input
    • target {"#####",
       "..#..",
       "#####",
       "..#..",
       "#####"}
    output
    Returns 5
  5. input
    • target {".#.#.",
       "#####",
       ".#.#.",
       "#####",
       ".#.#."}
    output
    Returns 8
  6. input
    • target {".##.####.####.#########.##..",
       "##.#.####################.##",
       ".##.###.##.###.###.###.###..",
       "#..###..#########..###.##.##",
       "####..#######.#.#####.######",
       "##.######.#..#.#############",
       "##.######.###########.######",
       "#######.#######.#..###.#.###",
       "#####..#######.#####.#.###.#",
       "#..#################.#.####.",
       "##.######..#.#####.######.##",
       "..#.#############.#.##....#.",
       "....##..##..#.#####.#.###.##",
       "##.#########...#..#.#.######",
       "##.#..###########..#..####.#",
       "#.####.###.########.########",
       "#####.#########.##.##.######",
       ".##.####..###.###...######.#"}
    output
    Returns 88
  7. input
    • target { "...................." }
    output
    Returns 0
    note
    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)2003, TopCoder, Inc. All rights reserved.