提高网站访问速度,wordpress 用户名 密码,微信平台开发费用,如何在百度做免费推广产品1. 题目
给你一个 m x n 的二进制矩阵 mat。
每一步#xff0c;你可以选择一个单元格并将它反转#xff08;反转表示 0 变 1 #xff0c;1 变 0 #xff09;。如果存在和它相邻的单元格#xff0c;那么这些相邻的单元格也会被反转。#xff08;注#xff1a;相邻的两个…1. 题目
给你一个 m x n 的二进制矩阵 mat。
每一步你可以选择一个单元格并将它反转反转表示 0 变 1 1 变 0 。如果存在和它相邻的单元格那么这些相邻的单元格也会被反转。注相邻的两个单元格共享同一条边。
请你返回将矩阵 mat 转化为全零矩阵的最少反转次数如果无法转化为全零矩阵请返回 -1 。
二进制矩阵的每一个格子要么是 0 要么是 1 。
全零矩阵是所有格子都为 0 的矩阵。 示例 1
输入mat [[0,0],[0,1]]
输出3
解释一个可能的解是反转 (1, 0)然后 (0, 1) 最后是 (1, 1) 。示例 2
输入mat [[0]]
输出0
解释给出的矩阵是全零矩阵所以你不需要改变它。示例 3
输入mat [[1,1,1],[1,0,1],[0,0,0]]
输出6示例 4
输入mat [[1,0,0],[1,0,0]]
输出-1
解释该矩阵无法转变成全零矩阵提示
m mat.length
n mat[0].length
1 m 3
1 n 3
mat[i][j] 是 0 或 1 。来源力扣LeetCode 链接https://leetcode-cn.com/problems/minimum-number-of-flips-to-convert-binary-matrix-to-zero-matrix 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. BFS解题
矩阵每个格子反转操作后都可以转换成数字检查它是否等于0状态先将初始状态push进队列visited访问记录该状态编码成数字然后依次更改矩阵的每个位置如果更改后的状态没出现过push进队列遇见状态0的时候停止BFS返回BFS的层数即最少反转次数
class Solution {vectorvectorint dir {{1,0},{0,1},{0,-1},{-1,0},{0,0}};//反转操作位置int m, n;
public:int minFlips(vectorvectorint mat) {m mat.size(), n mat[0].size();int num matToNum(mat), step 0, size, i, j;if(num 0)return step;unordered_setint visited;//访问过了的状态queueint q;visited.insert(num);q.push(num);while(!q.empty()){step;//bfs步数size q.size();while(size--){numToMat(q.front(),mat);//将数字解码成矩阵matq.pop();for(i 0; i m; i)//mat的每个位置都可以操作{for(j 0; j n; j){ //每个位置进行反转操作flip(mat,i,j);num matToNum(mat);//将矩阵状态编码成numif(num 0)return step;if(!visited.count(num))//这种状态没有访问过{visited.insert(num);//访问标记q.push(num);//加入队列}flip(mat,i,j);//恢复现场,进行下个位置反转}}}}return -1;}int matToNum(vectorvectorint M){ //矩阵编码成数字int num 0, i, j;for(i 0; i m; i)for(j 0; j n; j)num num*2M[i][j];return num;}void numToMat(int num, vectorvectorint M){ //数字解码成矩阵int bit, i, j;for(i m-1; i 0; i--)for(j n-1; j 0; j--){M[i][j] (num1);//取最低位num 1;//数字右移1位}}void flip(vectorvectorint M, int i, int j){ //反转i,j位置及其周围4个位置int x, y, k;for(k 0; k 5; k){x idir[k][0];y jdir[k][1];if(x0 xm y0 yn)M[x][y] 1-M[x][y];}}
};
