【算法】Transform to Chessboard 变为棋盘

Transform to Chessboard 变为棋盘

问题描述：

一个 n x n 的二维网络 board 仅由 0 和 1 组成 。每次移动，你能任意交换两列或是两行的位置。

返回 将这个矩阵变为 棋盘 所需的最小移动次数 。如果不存在可行的变换，输出 -1。

棋盘 是指任意一格的上下左右四个方向的值均与本身不同的矩阵。

n的范围 [ 2,30]

分析

这是一个比较难想的问题，NN的矩阵中要把矩阵通过相邻行或者相邻列交换的方式，最终变成棋盘。
因为限定了必须是相邻行或者相邻列，所以有些特性就必须先抽出来。
当进行swap row时，同一列的元素是不变的，同理swap col时，同一行的元素也是不变的。
让n=2,很明显要是能最终变成棋盘，这2行的元素一定是满足01互补的，其次还会满足10交替或者01交替。
以行为角度，其必须满足只有2种类型的行，而且他们一定是互补的。其次 每一列 和每一行的01数量要满足其对应的棋盘。
因此需要解决的2个问题
1 最终能否变成棋盘
2 如何变成棋盘要移动的最少次数。
需要先通过 必要条件的判断，保证 矩阵最终可以变成棋盘，然后再对矩阵计算。
判断条件
1 行与列的种类必须是2，否则无解
2 A行的0数量一定与B行中1数量相等，
3 n为odd时，1开头，cnt1-cnt0=1,0开头 cnt0-cnt1=1。
n为even时，cnt1=cnt0

如果满足以上条件，说明矩阵最终可以变成棋盘。
而过程，可以是先行后列，或者先列后行，并且实际上只需要考虑第一行和第一列的移动次数。
对于第一行，0或者1开头，一旦第一行移动完成01间隔，为了实现01间隔，实际操作的是相邻列的移动，那么列就已经固定。
同理对于第一列，也是一样。
因为n的范围不超过30，可以利用位运算，将每一行的01状态用数字x表示，同时将目标的状态用y表示。
x^y中1的数量表示需要交换的行/列数。
因为最终的结果是0或者1开头，预设最终结果为tar 以1开头，对于row来说，有2种类型，r1,r2最终变成tar的移动次数可能不一样，最理想的一定是选移动次数最小的，对于col来说，也是一个道理。

代码

class Solution {int n = 0, INF = 0x3f3f3f3f;int getCnt(int a, int b) {return Integer.bitCount(a) != Integer.bitCount(b) ? INF : Integer.bitCount(a ^ b) / 2;}public int movesToChessboard(int[][] g) {n = g.length;int r1 = -1, r2 = -1, c1 = -1, c2 = -1, mask = (1 << n) - 1;for (int i = 0; i < n; i++) {int a = 0, b = 0;for (int j = 0; j < n; j++) {if (g[i][j] == 1) a += (1 << j);if (g[j][i] == 1) b += (1 << j);}if (r1 == -1) r1 = a;else if (r2 == -1 && a != r1) r2 = a;if (c1 == -1) c1 = b;else if (c2 == -1 && b != c1) c2 = b;if (a != r1 && a != r2) return -1;if (b != c1 && b != c2) return -1;}if (r2 == -1 || c2 == -1) return -1;if ((r1 ^ r2) != mask || (c1 ^ c2) != mask) return -1;int t = 0;for (int i = 0; i < n; i += 2) t += (1 << i);int ans = Math.min(getCnt(r1, t), getCnt(r2, t)) + Math.min(getCnt(c1, t), getCnt(c2, t));return ans >= INF ? -1 : ans;}
}

时间复杂度 O($N^2$)
空间复杂度： O(1)

代码 来源于 三叶大佬，值得学习

Tag

Array Matrix Bit