C++ 中将二进制矩阵转换为零矩阵所需的最小翻转次数


假设我们有一个 m x n 的二进制矩阵 mat。一步之内,我们可以选择一个单元格并翻转其位及其所有四个邻居(如果存在)。我们必须找到将 mat 转换为零矩阵所需的最小步数。如果没有解决方案,则返回 -1。

因此,如果给定的输入类似于 [[0,0], [0,1]],则更改将类似于 -

所以我们需要 3 步,输出将是 3。

为了解决这个问题,我们将遵循以下步骤 -

  • n := 行数,m := 列数,x := 0
  • 初始化 i := 0,当 i < n 时,更新(i 增加 1),执行 -
    • 初始化 j := 0,当 j < m 时,更新(j 增加 1),执行 -
      • 初始化 j := 0,当 j < m 时,更新(j 增加 1),执行 -
        • x := x + 将 mat[i][j] 的值左移 (i * m) + j) 次
  • 定义一个包含 2^(n * m) 个单元格的数组 dp,并将其全部填充为 -1
  • dp[x] := 0
  • 定义一个队列 q
  • 将 x 插入 q
  • 当 (q 不为空) 时,执行 -
  • current := q 的第一个元素,从 q 中删除该元素
  • 如果 current 等于 0,则 -
    • 返回 dp[current]
  • 初始化 i := 0,当 i < n 时,更新(i 增加 1),执行 -
    • 初始化 j := 0,当 j < m 时,更新(j 增加 1),执行 -
      • temp := current
      • temp := temp XOR 2^ (i * m) + j)
      • 初始化 k := 0,当 k < 4 时,更新(k 增加 1),执行 -
        • ni := i + dir[k][0]
        • nj := j + dir[k][1]
        • 如果 ni < 0 或 nj < 0 或 ni >= n 或 nj >= m,则 -
          • 忽略以下部分,跳到下一次迭代
          • temp := temp XOR 2^ (ni * m) + nj)
      • 如果 dp[temp] 等于 -1,则 -
        • dp[temp] := dp[current] + 1
        • 将 temp 插入 q
  • 返回 -1

让我们看看以下实现以获得更好的理解 -

示例

 实时演示

#include <bits/stdc++.h>
using namespace std;
int dir[4][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
class Solution {
public:
   int minFlips(vector<vector<int>>& mat) {
      int n = mat.size();
      int m = mat[0].size();
      int x = 0;
      for(int i = 0; i < n; i++){
         for(int j = 0; j < m; j++){
            x += (mat[i][j] << ((i * m) + j));
         }
      }
      vector < int > dp(1 << (n*m), -1);
      dp[x] = 0;
      queue <int> q;
      q.push(x);
      while(!q.empty()){
         int current = q.front();
         q.pop();
         if(current == 0)return dp[current];
         for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
               int temp = current;
               temp ^= (1 << ((i *m) + j));
               for(int k = 0; k < 4; k++){
                  int ni = i + dir[k][0];
                  int nj = j + dir[k][1];
                  if(ni < 0 || nj < 0 || ni >= n || nj >= m)continue;
                  temp ^= (1 << ((ni *m) + nj));
               }
               if(dp[temp] == -1){
                  dp[temp] = dp[current] + 1;
                  q.push(temp);
               }
            }
         }
      }
      return -1;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{0,0},{0,1}};
   cout << (ob.minFlips(v));
}

输入

{{0,0},{0,1}}

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

输出

3

更新于: 2020年6月2日

132 次查看

开启您的 职业生涯

通过完成课程获得认证

开始
广告