【数学】【网格】【状态压缩】782 变为棋盘-阿里云开发者社区

本文涉及知识点

数学网格状态压缩

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

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛

测试环境

操作系统：win7 开发环境： VS2019 C++17

或者操作系统：win10 开发环境： VS2022 **C+

+17**

如无特殊说明，本算法用**C++**实现。

【数学】【网格】【状态压缩】782 变为棋盘

本文涉及知识点

LeetCode:782 变为棋盘

数学

代码

核心代码

测试用例

2023年4月版

扩展阅读

视频课程

相关

测试环境

热门文章

最新文章

相关电子书

相关实验场景