Connection Status:
Competition Arena > YetAnotherBoardGame

YetAnotherBoardGame

SRM 581 · 2012-12-13 · by gojira_tc

SRM 581 · 2012-12-13 · by gojira_tc · Brute Force
Class Name: YetAnotherBoardGame
Return Type: int
Method Name: minimumMoves
Arg Types: (vector<string>)
Problem Statement

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:
  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.

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)
{"BBW",
 "WWW",
 "BWW"}
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)
{"WBW",
 "BBW",
 "WBW"}
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

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

Coding Area

Language: C++17 · define a public class YetAnotherBoardGame with a public method int minimumMoves(vector<string> board) · 121 test cases · 2 s / 256 MB per case

Submitting as anonymous