<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>



// 1 1 0
// 0 0 1
// 0 0 1

// 0 1 0
// 1 0 1
// 0 1 0

class Solution {
public:
    int movesToChessboard(vector<vector<int>>& board) {
        // treat rows and cols as sep problem
        // treat even and odd as slighlyt sep
        int n = board.size(), m = board[0].size();
        
        // rows
        unordered_map<string, int> row_seen;
        for(int i = 0; i < n; ++i){
            string row;
            int balance = 0;
            for(int j = 0; j < m; ++j){
                row.push_back(board[i][j] + '0');

                if(board[i][j] == 0){
                    ++balance;
                } else {
                    --balance;
                }
            }

            if(abs(balance) >= 2){
                return -1;
            }

            row_seen[row]++;
        }

        int global = 0;

        unordered_map<string, int> col_seen;
        for(int i = 0; i < m; ++i){
            string col;
            int balance = 0;

            for(int j = 0; j < n; ++j){
                col.push_back(board[j][i] + '0');

                if(board[j][i] == 0){
                    ++balance;
                    ++global;
                } else {
                    --balance;
                    --global;
                }
            }

            if(abs(balance) >= 2){
                return -1;
            }

            col_seen[col]++;
        }


        if(col_seen.size() != 2 || row_seen.size() != 2){
            return -1;
        }

        bool even = board.size() % 2 == 0;

        if(even && global != 0){
            return -1;
        }

        if(!even && abs(global) != 1){
            return -1;
        }


        int a = 0, b = 1;
        int diff1 = 0;
        int diff2 = 0;

        // row
        for(int i = 0; i < n; ++i){
            if(board[i][0] == a){
                ++diff2;
            } else {
                ++diff1;
            }

            swap(a, b);
        }

        int d = min(diff1, diff2);

        if(d % 2 == 1){
            d = max(diff1, diff2);
        }
    
        int tot = d / 2;

        a = 0, b = 1;
        diff1 = 0;
        diff2 = 0;

        for(int i = 0; i < m; ++i){
            if(board[0][i] == a){
                ++diff2;
            } else {
                ++diff1;
            }

            swap(a, b);
        }
        
        // cout << tot << endl;
        d = min(diff1, diff2);

        if(d % 2 == 1){
            d = max(diff1, diff2);
        }
    
        tot += d / 2;
        return tot;
    }
};
13500