Problem Statement | | | 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:
- 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.
- 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 | | | | Class: | YetAnotherBoardGame | | Method: | minimumMoves | | Parameters: | String[] | | Returns: | int | | Method signature: | int minimumMoves(String[] board) | | (be sure your method is public) |
| | | | | | Constraints | | - | board will contain between 1 and 13 elements, inclusive. | | - | Each element of board will be between 1 and 13 characters long, inclusive. | | - | The elements of board will be of the same length. | | - | Each element of board will consist of 'W' and 'B' characters only. | | | Examples | | 0) | | | | {"BBBBBBBBB",
"BBWBBBBBB",
"BWWWBBBBB",
"BBWBBBWBB",
"BBBBBWBWB",
"BBBBBBWBB"} |
| Returns: 2 | | A type 1 move on (4, 6) and a type 2 move on (2, 2) turn the whole board black. |
|
| | 1) | | | | | Returns: 2 | | Manao can perform a move of type 2 on cell (1, 2) and a move of type 1 on cell (2, 0). |
|
| | 2) | | | | | Returns: 4 | | 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). |
|
| | 3) | | | | {"BBBB",
"WBWB",
"BBBB",
"BBBB"} |
| Returns: -1 | | There is no way to turn this board black. |
|
| | 4) | | | | {"WWWWWBW",
"WBWBWBW",
"BBWBBWW"} |
| Returns: 7 | |
| | 5) | | | | {"WWWWWWWWWW",
"WWWWWWWWWW",
"WWWWWWWWWW",
"WWWWWWWWWW",
"WWWWWWWWWW",
"WWWWWWWWWW",
"WWWWWWWWWW",
"WWWWWWWWWW",
"WWWWWWWWWW",
"WWWWWWWWWW"}
|
| 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)2024, TopCoder, Inc. All rights reserved.
|
