LeetCode:1284. 转化为全零矩阵的最少反转次数 BFS
给你一个 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 。
思路
这种转化求最短的一眼bfs,(其实矩阵只有3x3,说不定dfs也可以,但是有bfs就不用dfs了)
用矩阵存储状态,那么我们每次要传递的状态是矩阵,这没什么,主要是剪枝不太好办,如果在不同层遇到同一矩阵,如何判断它在前面的层出现过?
这里将矩阵转为字符串,然后通过维护一张哈希set来记录已经出现过的矩阵(其实就是自己懒得写矩阵的哈希函数 )
那么状态有了,状态之间的转移也可以通过穷举位置来实现,那就直接bfs,然后如果搜到全0的矩阵,直接返回就是了
class Solution { public: // 将字符串Mat表示的矩阵的x,y坐标及其周边反转 void revs(string &Mat, int x, int y, int m, int n) { vector<string> mat(m); for(int i=0; i<m; i++) mat[i]=string(Mat.begin()+i*n, Mat.begin()+(i+1)*n); mat[x][y] = (mat[x][y]==0)?(1):(0); if(0<=x-1 && x-1<m && 0<=y && y<n) mat[x-1][y]=(mat[x-1][y]==0)?(1):(0); if(0<=x && x<m && 0<=y-1 && y-1<n) mat[x][y-1]=(mat[x][y-1]==0)?(1):(0); if(0<=x+1 && x+1<m && 0<=y && y<n) mat[x+1][y]=(mat[x+1][y]==0)?(1):(0); if(0<=x && x<m && 0<=y+1 && y+1<n) mat[x][y+1]=(mat[x][y+1]==0)?(1):(0); for(int i=0; i<m; i++) for(int j=0; j<n; j++) Mat[i*n+j]=mat[i][j]; } int minFlips(vector<vector<int>>& mat) { int m=mat.size(), n=mat[0].size(), ans=0; string Mat, zero; for(int i=0; i<m; i++) for(int j=0; j<n; j++) { Mat+=(char)(mat[i][j]+0); zero+=0;} if(Mat==zero) return 0; unordered_set<string> vis; // 哈希set记录visited情况 queue<string> q; q.push(Mat); while(!q.empty()) { ans++; int qs = q.size(); for(int i=0; i<qs; i++) { string tp=q.front(); q.pop(); for(int x=0; x<m; x++) { for(int y=0; y<n; y++) { string next=tp; revs(next, x, y, m, n); if(vis.find(next)==vis.end()) { q.push(next); vis.insert(next);} if(next==zero) return ans; } } } } return -1; } };