# 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>& 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 & 1) rowSwaps = n - rowSwaps; if (colSwaps & 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 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 & 1: if rowSwaps & 1: rowSwaps = n - rowSwaps if colSwaps & 1: colSwaps = n - colSwaps else: rowSwaps = min(rowSwaps, n - rowSwaps) colSwaps = min(colSwaps, n - colSwaps) return (rowSwaps + colSwaps) // 2