1
class Solution {
2
  const int inf = 1e9;
3
  void transpose(vector<vector<int>> &board) {
4
    const int n = board.size();
5
    for (int i = 0; i < n; i++)
6
      for (int j = 0; j < i; j++) swap(board[i][j], board[j][i]);
7
  }
8

9
  bool isSame(vector<int> &r1, vector<int> &r2) {
10
    const int n = r1.size();
11
    for (int i = 0; i < n; i++)
12
      if (r1[i] != r2[i]) return false;
13
    return true;
14
  }
15

16
  bool isOpposite(vector<int> &r1, vector<int> &r2) {
17
    const int n = r1.size();
18
    for (int i = 0; i < n; i++)
19
      if (r1[i] == r2[i]) return false;
20
    return true;
21
  }
22

23
  int getSteps(vector<vector<int>> &&confusionMatrix) {
24
    int steps = inf;
25

26
    if (confusionMatrix[0][1] == confusionMatrix[1][0]) steps = confusionMatrix[0][1];
27

28
    if (confusionMatrix[0][0] == confusionMatrix[1][1]) steps = min(steps, confusionMatrix[0][0]);
29

30
    return steps;
31
  }
32

33
  vector<vector<int>> getConfusionMatrix(vector<int> &rowType) {
34
    const int n = rowType.size();
35
    vector<vector<int>> confusionMatrix(2, vector<int>(2, 0));
36
    for (int i = 0; i < n; i++) confusionMatrix[rowType[i]][i & 1]++;
37
    return confusionMatrix;
38
  }
39

40
  int solve1d(vector<int> &arr) {
41
    return getSteps(getConfusionMatrix(arr));
42
  }
43

44
  int makeColumnsAlternating(vector<vector<int>> &board) {
45
    const int n = board.size();
46
    vector<int> rowType(n, 0);
47
    for (int i = 1; i < n; i++)
48
      if (isOpposite(board[0], board[i]))
49
        rowType[i] = 1;
50
      else if (!isSame(board[0], board[i]))
51
        return inf;
52
    return solve1d(rowType);
53
  }
54

55
 public:
56
  int movesToChessboard(vector<vector<int>> &board) {
57
    int steps = makeColumnsAlternating(board);
58
    transpose(board);
59
    steps += makeColumnsAlternating(board);
60
    if (steps >= inf) return -1;
61
    return steps;
62
  }
63
};