力扣782——变为棋盘（数学模拟）

本文主要是介绍力扣782——变为棋盘（数学模拟），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

解题思路

行与行之间的交换，不会改变列内关系，同样列列交换不会改变行；
因此，只会有两种行，两种列，并且每行每列1，0的个数相等（n为奇数时相差1）；
并且这两行是相反的关系，只有这样交换完成后才会是两种相反的关系；
按此规则对矩阵进行合法判定；

交换次数即是与对应位置不等的个数/2；
之后分奇偶讨论：
偶数时，首位01皆可，且行与列没有关系，取两两组合中的最小值；
奇数时，首位字母是确定的，结束方案是确定的，交换次数应该从首位字母出现最多的行列确定：

例如[[1,1,0],[0,0,1],[0,0,1]] 首位应是0，行交换次数应从0，0，1得到，两位不同，交换一次；
列交换次数应从第一列1，0，0得到，两位不同交换一次；得到答案2；

具体见代码，需要自己举例推一推。

代码

class Solution {
public:
    int movesToChessboard(vector<vector<int>>& board) {
        int cnt0 = 0, n = board.size();
        vector<int> t0 = board[0];
        for(auto c : t0) if(c == 0) cnt0++;
        if(n % 2 == 0 && cnt0 != n / 2) return -1;
        if(n % 2 == 1 && !(cnt0 == n / 2 || cnt0 == n / 2 + 1)) return -1;
        vector<int> t1 = t0;
        for(int i = 0; i < n; i++) {
            t1[i] = !t0[i];
        }
        cnt0 = 0;
        for(int i = 0; i < n; i++) {
            if(board[i] == t0) cnt0++;
            if(board[i] != t0 && board[i] != t1) return -1;
        }
        if(n % 2 == 0 && cnt0 != n / 2) return -1;
        if(n % 2 == 1 && !(cnt0 == n / 2 || cnt0 == n / 2 + 1)) return -1;

        int a = 0, b = 0, ans = 0, tmp = 0;
        for(int i = 0; i < n; i++) {
            if(i % 2 != t0[i]) a++;  //首位是0的情况下不满足的位置
        }
        for(int i = 0; i < n; i++) {
            if(i % 2 != board[i][0]) b++;
        }       
        //偶数个，首位0，1都可，取最小值
        if(n % 2 == 0) return min({a + b, 2 * n - a - b, a + n - b, b + n - a}) / 2;
        //奇数个，最后形态确定，先看哪种形态，统计交换次数
        cnt0 = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(board[i][j] == 0) cnt0++;
            }
        }
        if(cnt0 == n * n / 2 + 1) { //首位是0
            for(int i = 0; i < n; i++) {
                if(t0[i] == 0) tmp++;
            }
            //最多的是0
            if(tmp == n / 2 + 1) ans += a;
            else ans += n - a;
            tmp = 0;
            for(int i = 0; i < n; i++) {
                if(board[i][0] == 0) tmp++;
            }
            if(tmp == n / 2 + 1) ans += b;
            else ans += n - b;
        }
        else {
            for(int i = 0; i < n; i++) {
                if(t0[i] == 1) tmp++;
            }
            //最多的是1
            if(tmp == n / 2 + 1) ans += n - a;
            else ans += a;
            tmp = 0;
            for(int i = 0; i < n; i++) {
                if(board[i][0] == 1) tmp++;
            }
            if(tmp == n / 2 + 1) ans += n - b;
            else ans += b;
        }
        return ans / 2;
    }
};

这篇关于力扣782——变为棋盘（数学模拟）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！