Skip to content

782. Transform to Chessboard

  • Time: $O(n^2)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
 public:
  int movesToChessboard(vector<vector<int>>& board) {
    const int n = board.size();
    int rowSum = 0;
    int colSum = 0;
    int rowSwaps = 0;
    int colSwaps = 0;

    for (int i = 0; i < n; ++i)
      for (int j = 0; j < n; ++j)
        if (board[0][0] ^ board[i][0] ^ board[0][j] ^ board[i][j] == 1)
          return -1;

    for (int i = 0; i < n; ++i) {
      rowSum += board[0][i];
      colSum += board[i][0];
    }

    if (rowSum != n / 2 && rowSum != (n + 1) / 2)
      return -1;
    if (colSum != n / 2 && colSum != (n + 1) / 2)
      return -1;

    for (int i = 0; i < n; ++i) {
      rowSwaps += board[i][0] == (i & 1);
      colSwaps += board[0][i] == (i & 1);
    }

    if (n % 2 == 1) {
      if (rowSwaps % 2 == 1)
        rowSwaps = n - rowSwaps;
      if (colSwaps % 2 == 1)
        colSwaps = n - colSwaps;
    } else {
      rowSwaps = min(rowSwaps, n - rowSwaps);
      colSwaps = min(colSwaps, n - colSwaps);
    }

    return (rowSwaps + colSwaps) / 2;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
  public int movesToChessboard(int[][] board) {
    final int n = board.length;
    int rowSum = 0;
    int colSum = 0;
    int rowSwaps = 0;
    int colSwaps = 0;

    for (int i = 0; i < n; ++i)
      for (int j = 0; j < n; ++j)
        if ((board[0][0] ^ board[i][0] ^ board[0][j] ^ board[i][j]) == 1)
          return -1;

    for (int i = 0; i < n; ++i) {
      rowSum += board[0][i];
      colSum += board[i][0];
    }

    if (rowSum != n / 2 && rowSum != (n + 1) / 2)
      return -1;
    if (colSum != n / 2 && colSum != (n + 1) / 2)
      return -1;

    for (int i = 0; i < n; ++i) {
      if (board[i][0] == (i & 1))
        ++rowSwaps;
      if (board[0][i] == (i & 1))
        ++colSwaps;
    }

    if (n % 2 == 1) {
      if (rowSwaps % 2 == 1)
        rowSwaps = n - rowSwaps;
      if (colSwaps % 2 == 1)
        colSwaps = n - colSwaps;
    } else {
      rowSwaps = Math.min(rowSwaps, n - rowSwaps);
      colSwaps = Math.min(colSwaps, n - colSwaps);
    }

    return (rowSwaps + colSwaps) / 2;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
  def movesToChessboard(self, board: list[list[int]]) -> int:
    n = len(board)

    if any(board[0][0] ^ board[i][0] ^ board[0][j] ^ board[i][j]
           for i in range(n) for j in range(n)):
      return -1

    rowSum = sum(board[0])
    colSum = sum(board[i][0] for i in range(n))

    if rowSum != n // 2 and rowSum != (n + 1) // 2:
      return -1
    if colSum != n // 2 and colSum != (n + 1) // 2:
      return -1

    rowSwaps = sum(board[i][0] == (i & 1) for i in range(n))
    colSwaps = sum(board[0][i] == (i & 1) for i in range(n))

    if n % 2 == 1:
      if rowSwaps % 2 == 1:
        rowSwaps = n - rowSwaps
      if colSwaps % 2 == 1:
        colSwaps = n - colSwaps
    else:
      rowSwaps = min(rowSwaps, n - rowSwaps)
      colSwaps = min(colSwaps, n - colSwaps)

    return (rowSwaps + colSwaps) // 2