back to the menu

Flag Counter TopCoder SRM 581 - 900: YetAnotherBoardGame

SRM 581 1 900 YetAnotherBoardGame


Problem Statement

给一个N*M的黑白棋盘,你的目标是把它们都变成黑色,每次可以对一个点进行两种操作。
1.以他为中心的十字型区域颜色全部取反
2.以他为中心的十字型区域除了自己颜色全部取反
并且每行每列都不能进行不同种类的操作,问最少进行多少操作完成,如果不能返回-1

Manao is playing a new board game. The game is played on an NxM board with each cell initially colored either black or white. The cell on the intersection of the i-th (0-based) row and j-th (0-based) column is referred to as (i, j).

Manao may perform two types of moves:
  1. Pick a cell (i, j) (0 ≤ i < N, 0 ≤ j < M) and toggle the color of cells (i-1, j), (i+1, j), (i, j-1), (i, j+1). If some of these cells are outside the board, the move is considered valid, and the cells outside of the board are ignored.
  2. Pick a cell (i, j) (0 ≤ i < N, 0 ≤ j < M) and toggle the color of cells (i, j), (i-1, j), (i+1, j), (i, j-1), (i, j+1). Again, the cells outside of the board, if any, are ignored.
We call the two move types "type 1 moves" and "type 2 moves". In both cases, we say that Manao performed the move on the cell (i, j).

Manao cannot perform the moves arbitrarily, he has to follow some additional constraints: For each row, all moves applied to cells in the row have to be of the same type. Also, for each column, all moves applied to cells in the column have to be of the same type. In particular, Manao is not allowed to perform a type 1 move on a cell and then a type 2 move on the same cell (nor vice versa).

You are given a String[] board consisting of N elements, each M characters long. The j-th character in the i-th row (0-based indices) of board is 'W' if cell (i, j) is initially white, and 'B' otherwise. Manao wants to turn the board all black. Determine the minimum number of moves he needs to perform to accomplish this task. If it is impossible to turn every cell on the board black, return -1.

Definition

(be sure your method is public)

Limits

Constraints

Test cases

  1. input
    • board {"BBBBBBBBB",
       "BBWBBBBBB",
       "BWWWBBBBB",
       "BBWBBBWBB",
       "BBBBBWBWB",
       "BBBBBBWBB"}
    output
    Returns 2
    note
    A type 1 move on (4, 6) and a type 2 move on (2, 2) turn the whole board black.
  2. input
    • board {"BBW",
       "WWW",
       "BWW"}
    output
    Returns 2
    note
    Manao can perform a move of type 2 on cell (1, 2) and a move of type 1 on cell (2, 0).
  3. input
    • board {"WBW",
       "BBW",
       "WBW"}
    output
    Returns 4
    note
    If no additional constraints were imposed, Manao would perform a type 1 move on (1, 0) and a type 2 move on (1, 2). However, these cells are in the same row and thus these moves are incompatible. Instead, Manao can perform four type 2 moves on cells (1, 0), (1, 1), (0, 2) and (2, 2).
  4. input
    • board {"BBBB",
       "WBWB",
       "BBBB",
       "BBBB"}
    output
    Returns -1
    note
    There is no way to turn this board black.
  5. input
    • board {"WWWWWBW",
       "WBWBWBW",
       "BBWBBWW"}
    output
    Returns 7
  6. input
    • board {"WWWWWWWWWW",
       "WWWWWWWWWW",
       "WWWWWWWWWW",
       "WWWWWWWWWW",
       "WWWWWWWWWW",
       "WWWWWWWWWW",
       "WWWWWWWWWW",
       "WWWWWWWWWW",
       "WWWWWWWWWW",
       "WWWWWWWWWW"}
    output
    Returns 30

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.