1. 題目

給你一個(gè) m x n 的二進(jìn)制矩陣 mat。

每一步，你可以選擇一個(gè)單元格并將它反轉(zhuǎn)（反轉(zhuǎn)表示 0 變 1 ，1 變 0 ）。如果存在和它相鄰的單元格，那么這些相鄰的單元格也會(huì)被反轉(zhuǎn)。（注：相鄰的兩個(gè)單元格共享同一條邊。）

請你返回將矩陣 mat 轉(zhuǎn)化為全零矩陣的最少反轉(zhuǎn)次數(shù)，如果無法轉(zhuǎn)化為全零矩陣，請返回 -1 。

二進(jìn)制矩陣的每一個(gè)格子要么是 0 要么是 1 。

全零矩陣是所有格子都為 0 的矩陣。

示例 1： 輸入：mat = [[0,0],[0,1]] 輸出：3 解釋：一個(gè)可能的解是反轉(zhuǎn) (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 解釋：該矩陣無法轉(zhuǎn)變成全零矩陣提示： 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
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

2. BFS解題

• 矩陣每個(gè)格子反轉(zhuǎn)操作后都可以轉(zhuǎn)換成數(shù)字，檢查它是否等于0（狀態(tài)）
• 先將初始狀態(tài)push進(jìn)隊(duì)列，visited訪問記錄該狀態(tài)（編碼成數(shù)字）
• 然后依次更改矩陣的每個(gè)位置，如果更改后的狀態(tài)沒出現(xiàn)過，push進(jìn)隊(duì)列
• 遇見狀態(tài)0的時(shí)候，停止BFS，返回BFS的層數(shù)，即最少反轉(zhuǎn)次數(shù)

class Solution {vector<vector<int>> dir ={{1,0},{0,1},{0,-1},{-1,0},{0,0}};//反轉(zhuǎn)操作位置int m, n; public:int minFlips(vector<vector<int>>& mat) {m = mat.size(), n = mat[0].size();int num = matToNum(mat), step = 0, size, i, j;if(num == 0)return step;unordered_set<int> visited;//訪問過了的狀態(tài)queue<int> q;visited.insert(num);q.push(num);while(!q.empty()){++step;//bfs步數(shù)size = q.size();while(size--){numToMat(q.front(),mat);//將數(shù)字解碼成矩陣matq.pop();for(i = 0; i < m; i++)//mat的每個(gè)位置都可以操作{for(j = 0; j < n; j++){ //每個(gè)位置進(jìn)行反轉(zhuǎn)操作flip(mat,i,j);num = matToNum(mat);//將矩陣狀態(tài)編碼成numif(num == 0)return step;if(!visited.count(num))//這種狀態(tài)沒有訪問過{visited.insert(num);//訪問標(biāo)記q.push(num);//加入隊(duì)列}flip(mat,i,j);//恢復(fù)現(xiàn)場,進(jìn)行下個(gè)位置反轉(zhuǎn)}}}}return -1;}int matToNum(vector<vector<int>>& M){ //矩陣編碼成數(shù)字int num = 0, i, j;for(i = 0; i < m; i++)for(j = 0; j < n; j++)num = num*2+M[i][j];return num;}void numToMat(int num, vector<vector<int>>& M){ //數(shù)字解碼成矩陣int bit, i, j;for(i = m-1; i >= 0; i--)for(j = n-1; j >= 0; j--){M[i][j] = (num&1);//取最低位num >>= 1;//數(shù)字右移1位}}void flip(vector<vector<int>>& M, int i, int j){ //反轉(zhuǎn)i,j位置，及其周圍4個(gè)位置int x, y, k;for(k = 0; k < 5; k++){x = i+dir[k][0];y = j+dir[k][1];if(x>=0 && x<m && y>=0 && y<n)M[x][y] = 1-M[x][y];}} };

總結(jié)

以上是生活随笔為你收集整理的LeetCode 1284. 转化为全零矩阵的最少反转次数（BFS 矩阵状态编码解码）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。