【LeetCode】 1284. Minimum Number of Flips to Convert Binary Matrix to Zero Matrix

Description

Given a m x n binary matrix mat. In one step, you can choose one cell and flip it and all the four neighbours of it if they exist (Flip is changing 1 to 0 and 0 to 1). A pair of cells are called neighboors if they share one edge.

Return the minimum number of steps required to convert mat to a zero matrix or -1 if you cannot.

Binary matrix is a matrix with all cells equal to 0 or 1 only.

Zero matrix is a matrix with all cells equal to 0.

給予一m x n的邏輯矩陣。每一步中，你可以選擇一個方格翻轉它和它周圍四個鄰近且存在的格子(翻轉就是1變0、0變1)。一對鄰近的格子是指它們共用同一條邊。

回傳你將mat全部轉為0所需要的最小步數，如果沒辦法變成零矩陣就回傳**-1**。

邏輯矩陣是指所有的格子都只會是0或是1。

零矩陣是指全部的格子都是0。

Example:

Example 1:

Input: mat = [[0,0],[0,1]]
Output: 3
Explanation: One possible solution is to flip (1, 0) then (0, 1) and finally (1, 1) as shown.


Example 2:

Input: mat = [[0]]
Output: 0
Explanation: Given matrix is a zero matrix. We don't need to change it.


Example 3:

Input: mat = [[1,1,1],[1,0,1],[0,0,0]]
Output: 6


Example 4:

Input: mat = [[1,0,0],[1,0,0]]
Output: -1
Explanation: Given matrix can't be a zero matrix

Solution

• 這是著名的關燈遊戲，可查詢light out puzzle應該會有大量文章。
• 同一格按兩次等於沒按，先按A或先按B結果都會一樣；所以只需要知道需要按那些格子即可。
• 該題目n和m都不會超過3，只需要暴力解即可。

Code

class Solution {
public:
    //TODO: For debug, show the matrix context.
    void show(vector<vector<int>>& mat)
    {
        int sx = mat[0].size();
        int sy = mat.size();
        for(int i = 0; i < sy; i++)
        {
            for(int j = 0; j < sx; j++)
                cout << mat[i][j] << " ";
            cout << endl;
        }
    }
    
    //TODO: Flip the cell you chosen and its neighboors.
    void trigger(vector<vector<int>>& mat,int x, int y)
    {
        int sx = mat[0].size() - 1;
        int sy = mat.size() - 1;
        
        mat[y][x] ^= 1;
        
        if(x != 0) mat[y][x-1] ^= 1;
        if(y != 0) mat[y-1][x] ^= 1;
        if(x !=sx) mat[y][x+1] ^= 1;
        if(y !=sy) mat[y+1][x] ^= 1;
    }
    
    //TODO: Check the matrix is equal to zero or not. 
    bool isZero(vector<vector<int>> mat)
    {
        int sx = mat[0].size();
        int sy = mat.size();
        for(int i = 0; i < sy; i++)
        {
            for(int j = 0; j < sx; j++)
                if(mat[i][j]!=0) return false;
        }
        return true;
    }
    
    int findMin(vector<vector<int>>& mat)
    {
        int sx = mat[0].size();
        int sy = mat.size();
        int min = 100;
        for(int k = 1; k < pow(2,sx*sy); k++)
        {
            vector<vector<int>> tempMat = mat;
            int temp = k;
            int count = 0;
            int score = 0;
            while(temp != 0)
            {
                if(temp%2==1)
                {
                    trigger(tempMat,count%sx,count/sx);
                    score++;
                }
                temp/=2;
                count++;
            }
            if(isZero(tempMat))
                min = min<score?min:score;
        }
        return min==100?-1:min;
    }
    
    int minFlips(vector<vector<int>>& mat) {
        if(isZero(mat)) return 0;
        //show(mat);
        return findMin(mat);
    }
};

tags: LeetCode C++