题目大意：
转化为全零矩阵的最少反转次数
给你一个 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 。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1284
解题思路分析：
这是一道变形的广度优先搜索bfs题目，在matrix当前状态下，我们有m*n种变换的可能性，m和n为矩阵的长和宽。分别变换矩阵上的每一个点，将变换后的状态存入到Queue中，便于下一次的变换。另外建立一个visited列表，避免重复操作，记录下已经变换过的状态，如果再遇到该状态可以无视。因为matrix最大是3乘3，数量级很小，我们可以利用二进制数来记录当前状态。比如[[1,0],[0,1]]可以记录为1001。同理[[0,0],[0,0]]为0。
当bfs中遇到状态为0时，说明已经找到结果，返回当前步数即可。
实现代码：
public int minFlips(int[][] mat) {
Queue<int[][]> q = new LinkedList<>(); // bfs用的Queue
List<Integer> visited = new ArrayList<>(); // 记录已访问过的状态
// 如果当前mat的状态为0（全0矩阵），返回0。
if(getKey(mat)==0) return 0;
// 将当前状态存入已访问数组
visited.add(getKey(mat));
// 将当前矩阵加入Queue
q.offer(mat);
// 返回结果
int res=0;
// 以下为bfs常规操作
// 当Queue数量大于0，一直bfs。
while(q.size()>0){
// 当前Queue的size
int count=q.size();
// 循环count次
while(count-->0){
// 取出queue中的一个矩阵
int[][] m = q.poll();
// 循环矩阵每一个点，对该点及四周进行变换操作
for(int i=0;i<m.length;i++){
for(int j=0;j<m[0].length;j++){
// 注意不要在原数组上进行操作。
// 先copy一份当前矩阵
int[][] copy=Arrays
.stream(m).map(el->el.clone()).toArray($->m.clone());
// 变换矩阵当前点的值
copy[i][j]=(copy[i][j]==1?0:1);
// 变换当前点四周的值（如果四周存在）
if(i>0) copy[i-1][j]=(copy[i-1][j]==1?0:1);
if(i<m.length-1) copy[i+1][j]=(copy[i+1][j]==1?0:1);
if(j>0) copy[i][j-1]=(copy[i][j-1]==1?0:1);
if(j<m[0].length-1) copy[i][j+1]=(copy[i][j+1]==1?0:1);
// 计算变换后的状态
int key=getKey(copy);
// 如果状态为0，返回。
if(key==0) return res+1;
// 若该状态不在已访问列表中
if(!visited.contains(key)){
// 将该状态存入已访问列表
visited.add(key);
// 将当前修改后的矩阵存入Queue
q.offer(copy);
}
}
}
}
res++; // 返回结果加一
}
return -1;
}
int getKey(int[][] m){
int key=0;
for(int i=0;i<m.length;i++){
for(int j=0;j<m[0].length;j++){
key|= (m[i][j]<<(i*m[0].length+j));
}
}
return key;
}本题解法执行时间为13ms。
Runtime: 13 ms, faster than 100.00% of Java online submissions for Minimum Number of Flips to Convert Binary Matrix to Zero Matrix.
Memory Usage: 36.2 MB, less than 100.00% of Java online submissions for Minimum Number of Flips to Convert Binary Matrix to Zero Matrix.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1284-minimum-number-of-flips-to-convert-binary-matrix-to-zero-matrix-解题思路分析/