1
class Solution {
2
  public int movesToChessboard(int[][] board) {
3
    int N = board.length, colToMove = 0, rowToMove = 0, rowOneCnt = 0, colOneCnt = 0;
4
    for (int i = 0; i < N; i++) {
5
      for (int j = 0; j < N; j++) {
6
        if (((board[0][0] ^ board[i][0]) ^ (board[i][j] ^ board[0][j])) == 1) {
7
          return -1;
8
        }
9
      }
10
    }
11
    for (int i = 0; i < N; i++) {
12
      rowOneCnt += board[0][i];
13
      colOneCnt += board[i][0];
14
      if (board[i][0] == i % 2) {
15
        rowToMove++;
16
      }
17
      if (board[0][i] == i % 2) {
18
        colToMove++;
19
      }
20
    }
21
    if (rowOneCnt < N / 2 || rowOneCnt > (N + 1) / 2) {
22
      return -1;
23
    }
24
    if (colOneCnt < N / 2 || colOneCnt > (N + 1) / 2) {
25
      return -1;
26
    }
27
    if (N % 2 == 1) {
28
      // we cannot make it when ..ToMove is odd
29
      if (colToMove % 2 == 1) {
30
        colToMove = N - colToMove;
31
      }
32
      if (rowToMove % 2 == 1) {
33
        rowToMove = N - rowToMove;
34
      }
35
    } else {
36
      colToMove = Math.min(colToMove, N - colToMove);
37
      rowToMove = Math.min(rowToMove, N - rowToMove);
38
    }
39
    return (colToMove + rowToMove) / 2;
40
  }
41
}