<p>You are given an <code>n x n</code> binary grid <code>board</code>. In each move, you can swap any two rows with each other, or any two columns with each other.</p>

<p>Return <em>the minimum number of moves to transform the board into a <strong>chessboard board</strong></em>. If the task is impossible, return <code>-1</code>.</p>

<p>A <strong>chessboard board</strong> is a board where no <code>0</code>&#39;s and no <code>1</code>&#39;s are 4-directionally adjacent.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/06/29/chessboard1-grid.jpg" style="width: 500px; height: 145px;" />
<pre>
<strong>Input:</strong> board = [[0,1,1,0],[0,1,1,0],[1,0,0,1],[1,0,0,1]]
<strong>Output:</strong> 2
<strong>Explanation:</strong> One potential sequence of moves is shown.
The first move swaps the first and second column.
The second move swaps the second and third row.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/06/29/chessboard2-grid.jpg" style="width: 164px; height: 165px;" />
<pre>
<strong>Input:</strong> board = [[0,1],[1,0]]
<strong>Output:</strong> 0
<strong>Explanation:</strong> Also note that the board with 0 in the top left corner, is also a valid chessboard.
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/06/29/chessboard3-grid.jpg" style="width: 164px; height: 165px;" />
<pre>
<strong>Input:</strong> board = [[1,0],[1,0]]
<strong>Output:</strong> -1
<strong>Explanation:</strong> No matter what sequence of moves you make, you cannot end with a valid chessboard.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == board.length</code></li>
	<li><code>n == board[i].length</code></li>
	<li><code>2 &lt;= n &lt;= 30</code></li>
	<li><code>board[i][j]</code> is either&nbsp;<code>0</code> or <code>1</code>.</li>
</ul>

class Solution:
    def movesToChessboard(self, board):
        n = len(board)
        pat1, pat2 = [i % 2 for i in range(n)], [(i + 1) % 2 for i in range(n)]
        visited = [[False] * n for _ in range(n)]
        rowSwaps = colSwaps = 0
        
        for i in range(n):
            rowCount = colCount = 0
            for j in range(n):
                rowCount += board[i][j]
                colCount += board[j][i]
                if not visited[i][j]:
                    queue = [(i, j)]
                    visited[i][j] = True
                    val = board[i][j]
                    minRow = maxRow = i
                    minCol = maxCol = j
                    cells = 0
                    while queue:
                        x, y = queue.pop()
                        cells += 1
                        minRow, maxRow = min(minRow, x), max(maxRow, x)
                        minCol, maxCol = min(minCol, y), max(maxCol, y)
                        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                            newX, newY = x + dx, y + dy
                            if 0 <= newX < n and 0 <= newY < n and not visited[newX][newY] and board[newX][newY] == val:
                                visited[newX][newY] = True
                                queue.append((newX, newY))
                    if (maxRow - minRow + 1) * (maxCol - minCol + 1) != cells:
                        return -1

            if n % 2 == 0:
                if rowCount != n // 2 or colCount != n // 2:
                    return -1
            else:
                if not (rowCount in {n // 2, n // 2 + 1}) or not (colCount in {n // 2, n // 2 + 1}):
                    return -1

            if i == 0:
                rowSwaps = self.countSwaps(board[0], pat1, pat2)
                colSwaps = self.countSwaps([board[k][0] for k in range(n)], pat1, pat2)
                if rowSwaps == float('inf') or colSwaps == float('inf'):
                    return -1

        return rowSwaps + colSwaps

    def countSwaps(self, row, pat1, pat2):
        n = len(row)
        mismatch1 = sum(1 for i in range(n) if row[i] != pat1[i])
        mismatch2 = sum(1 for i in range(n) if row[i] != pat2[i])
        return min(mismatch1 // 2 if mismatch1 % 2 == 0 else float('inf'),
                   mismatch2 // 2 if mismatch2 % 2 == 0 else float('inf'))
16800