本文涉及知识点
数学 网格 状态压缩
LeetCode:782 变为棋盘
一个 n x n 的二维网络 board 仅由 0 和 1 组成 。每次移动，你能任意交换两列或是两行的位置。
返回 将这个矩阵变为 “棋盘” 所需的最小移动次数 。如果不存在可行的变换，输出 -1。
“棋盘” 是指任意一格的上下左右四个方向的值均与本身不同的矩阵。
示例 1:
输入: board = [[0,1,1,0],[0,1,1,0],[1,0,0,1],[1,0,0,1]]
输出: 2
解释:一种可行的变换方式如下，从左到右：
第一次移动交换了第一列和第二列。
第二次移动交换了第二行和第三行。
示例 2:
输入: board = [[0, 1], [1, 0]]
输出: 0
解释: 注意左上角的格值为0时也是合法的棋盘，也是合法的棋盘.
示例 3:
输入: board = [[1, 0], [1, 0]]
输出: -1
解释: 任意的变换都不能使这个输入变为合法的棋盘。
提示：
n == board.length
n == board[i].length
2 <= n <= 30
board[i][j] 将只包含 0或 1
数学
分两步：
一，调整列。
col0记录列首元素为0的列下标，col1记录列首元素为1的列下标。 col0(col1)中的各列必须完全相同,col0和col1相同行的元素必须不同。
如果n是偶数,调整的次数 = min(d0,d1)，c0和c1为首列，不影响后续结果。
二，调整行。
各列调整后，各行一定是{0,1,0,1⋯ \cdots⋯} 或 { 1,0,1,1⋯ \cdots⋯}，且数量相等。
调整后首列首元素的出现次数f0 ,必须等于 n - n/2。
行数从0开始。e0 为首（第0个）元素不在偶数行的数量，e1为第1个元素不在偶数行的数量。
如果n是偶数，调整行的次数：min(n/2-e0,m/2-e1)
如果n是奇数，调整行的次数：f0 - e0。
代码
125行代码，出错三次后，才搞定。强烈不推荐，细节太多。
核心代码
class Solution { public: int movesToChessboard(vector<vector<int>>& board) { const int n = board.size(); vector<int> col0, col1; for (int c = 0; c < n; c++) { if (board[0][c]) { col1.emplace_back(c); } else { col0.emplace_back(c); } } for (int inx :col0) { if (!SameCol(board, col0.front(), inx)) { return -1; } } for (int inx : col1) { if (!SameCol(board, col1.front(), inx)) { return -1; } } if (abs((int)col0.size() - (int)col1.size()) > 1 ) { return -1; } for (int r = 0; r < n; r++) { if (1 != board[r][col0.front()] + board[r][col1.front()]) { return -1; } } int d0 = EvenCnt(col0); int d1 = EvenCnt(col1); int iRet = 0,e0=0,e1=0,f0=0; auto Tmp = [&](int col) { e0 = CntByValue(board, col, board[0][col], 2); e1 = CntByValue(board, col, board[0][col] ^ 1, 2); f0 = CntByValue(board, col, board[0][col], 1); }; if (n & 1) { int iFirstCol = 0; if (col0.size() == col1.size() + 1) { iRet += (n/2+1-d0); iFirstCol = col0.front(); } else if (col1.size() == col0.size() + 1) { iRet += (n/2+1-d1); iFirstCol = col1.front(); } else { return -1; } Tmp(iFirstCol); if (f0 == n / 2 + 1) { iRet += (n/2+1-e0); } else if (f0 == n / 2) { iRet += (n/2+1-e1); } else { return -1; } } else { Tmp(0); if (f0 != (n - n / 2)) { return -1; } iRet += min(n / 2 - d0, n / 2 - d1); iRet += min(n / 2 - e0, n/2 - e1); } return iRet; } int EvenCnt(const vector<int>& indexs)const { int iRet = 0; for (const auto& inx : indexs) { iRet += (0 == inx % 2); } return iRet; } bool SameCol(vector<vector<int>>& board, int col1, int col2) { for (int r = 0; r < board.size(); r++) { if (board[r][col1] != board[r][col2]) { return false; } } return true; } int CntByValue(vector<vector<int>>& board, int col,int value ,int setp=2) {//指定值在偶数行的数量 int iRet = 0; for (int r = 0; r < board.size(); r += setp) { iRet += (board[r][col] == value); } return iRet; } };
测试用例
template<class T,class T2> void Assert(const T& t1, const T2& t2) { assert(t1 == t2); } template<class T> void Assert(const vector<T>& v1, const vector<T>& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { Assert(v1[i], v2[i]); } } int main() { vector<vector<int>> board; { Solution sln; board = { {1,1,1,0},{1,1,1,0},{0,0,0,1},{0,0,0,1} }; auto res = sln.movesToChessboard(board); Assert(-1, res); } { Solution sln; board = { {1,1,1,1},{1,1,1,1},{0,0,0,0},{0,0,0,0} }; auto res = sln.movesToChessboard(board); Assert(-1, res); } { Solution sln; board = { {1, 1, 0}, { 0,0,1 }, { 0,0,1 }}; auto res = sln.movesToChessboard(board); Assert(2, res); } { Solution sln; board = { {0,1,1,0},{0,1,1,0},{1,0,0,1},{1,0,0,1} }; auto res = sln.movesToChessboard(board); Assert(2, res); } { Solution sln; board = { {0, 1}, {1, 0} }; auto res = sln.movesToChessboard(board); Assert(0, res); } { Solution sln; board = { {1, 0}, {1, 0} }; auto res = sln.movesToChessboard(board); Assert(-1, res); } }
2023年4月版
用状态压缩，可以大幅降低难道。
class Solution { public: int movesToChessboard(vector<vector>& board) { m_iN = board.size(); const int iRowMask = MaskRow(board[0]); const int iColMask = MaskCol(board,0); int iForRevrver = (1 << m_iN) - 1; const int iRevRowMask = iRowMask ^ iForRevrver; const int iRevColMask = iColMask ^ iForRevrver; int iRowCnt = 0, iColCnt = 0; for (int i = 0; i < m_iN; i++) { const int iCurRowMask = MaskRow(board[i]); if ((iCurRowMask != iRowMask) && (iCurRowMask != iRevRowMask)) { return -1; } iRowCnt += (iCurRowMask == iRowMask); const int iCurColMask = MaskCol(board, i); if ((iCurColMask != iColMask) && (iCurColMask != iRevColMask)) { return -1; } iColCnt += (iCurColMask == iColMask); } int iMoveRow = GetMove(iRowMask, iRowCnt); int iMoveCol = GetMove(iColMask, iColCnt); if ((-1 == iMoveRow) || (-1 == iMoveCol)) { return -1; } return iMoveRow + iMoveCol; } int GetMove(int iMask, int iCnt) { const int iOneBitNum = bitcount(iMask); if (m_iN & 1) {//奇数 if (1 != abs(m_iN - iCnt * 2)) { return -1; } if (1 != abs(m_iN - iOneBitNum * 2)) { return -1; } if (iOneBitNum == m_iN / 2) {//奇数位0，偶数位为1 return m_iN / 2 - bitcount(iMask & 0xAAAAAAAA); } else { return m_iN / 2 + 1 - bitcount(iMask & 0x55555555); } } else { if (iCnt != m_iN / 2) { return -1; } if (iOneBitNum != m_iN / 2) { return -1; } //最低位编号为1，次最低为编号为2… 奇数位为1，需要移动的次数 int iMove1 = m_iN / 2 - bitcount(iMask & 0x55555555); //偶数为为1 int iMove2 = m_iN / 2 - bitcount(iMask & 0xAAAAAAAA); return min(iMove1, iMove2); } } int MaskRow(const vector& vRow) { int iRet = 0; for (int i = 0; i < m_iN; i++) { if (vRow[i]) { iRet |= (1 << i); } } return iRet; } int MaskCol(const vector<vector>& board, int iCol) { int iRet = 0; for (int i = 0; i < m_iN; i++) { if (board[i][iCol]) { iRet |= (1 << i); } } return iRet; } int m_iN; };
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关
下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 我想对大家说的话 |
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 **C+
+17**
如无特殊说明，本算法用**C++**实现。
