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