# 1284. Minimum Number of Flips to Convert Binary Matrix to Zero Matrix
###### tags: `Leetcode` `Hard` `Backtracking`
Link: https://leetcode.com/problems/minimum-number-of-flips-to-convert-binary-matrix-to-zero-matrix/description/
## 思路
backtracking
穷举每个元素是否flip
## Code

class Solution {
    public int minFlips(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        int ans = Integer.MAX_VALUE;
        for(int state=0; state<(1<<(m*n)); state++){
            if(check(state, mat)){
                ans = Math.min(ans, Integer.bitCount(state));
            }
        }
        if(ans==Integer.MAX_VALUE) return -1;
        return ans;
    }
    private boolean check(int state, int[][] mat){
        int m = mat.length, n = mat[0].length;
        int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1},{0,0}};
        int[][] temp = new int[m][n];
        for(int i=0; i<m; i++) temp[i] = mat[i].clone();
        
        for(int s=0; s<m*n; s++){
            if(((state>>s)&1)==0) continue;
            int i = s/n;
            int j = s%n;
            for(int[] dir:dirs){
                int nextx = i+dir[0], nexty = j+dir[1];
                if(nextx>=0 && nextx<m && nexty>=0 && nexty<n){
                    temp[nextx][nexty] = 1-temp[nextx][nexty];
                }
            }
        }
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(temp[i][j]!=0) return false;
            }
        }
        return true;
    }
}