Leetcode 1284: Minimum Number of Flips to Convert Binary Matrix to Zero Matrix

https://leetcode.com/problems/minimum-number-of-flips-to-convert-binary-matrix-to-zero-matrix/description/

Notes:

This question seems very complicated, which is labeled as hard. But actually it can be solved by the BFS. The size of the matrix is very small, so it is doable by the BFS.

The BFS method is known to find the length of the shortest path(s).

For this question, in order to better memorize the visited "conditions", we can convert the matrix into a string.

Some details for the indexes: if an element has a position of (x, y) in matrix which has m rows and n columns, then the corresponding index in the string is x*n + y. We can also recalculate the position of the element in the matrix if we only know the index in the string.

As required by the question, when we flip on element in the matrix, we need to flip all its four neighbors, which is a very typical operation in the BFS. Since we have converted the matrix into a string, we need to pay attention to the indexes using the above formula.

As mentioned above, a hash table will be used to memorize the visited "string", and the target is the string with all '0' chars of the correct length (m*n).

Then we can perform a layer-by-layer BFS. If the target can be found during search, return the number of the layers; otherwise, return -1.

See the code below:

class Solution {
public:
    int minFlips(vector<vector<int>>& mat) {
        int res = 0, m = mat.size(), n = mat[0].size();
        string s = "", end = "";
        for(auto &a : mat) {
            for(auto &b : a) {
                s.push_back(b+'0');
                end.push_back('0');
            }
        }
        if(s == end) return res;
        queue<string> q;
        unordered_map<string, int> mp;
        vector<int> dirs = {-1, 0, 1, 0, -1};
        q.push(s);
        mp[s] = 1;
        while(q.size()) {
            ++res;
            int k = q.size();
            for(int i=0; i<k; ++i) {
                auto t = q.front();
                q.pop();
                for(int j=0; j<t.size(); ++j) {
                    string st = t;
                    if(st[j] == '0') st[j] = '1';
                    else st[j] = '0';
                    int x = j/n, y = j%n;
                    for(int z = 0; z+1<dirs.size(); ++z) {
                        int nx = x + dirs[z], ny = y + dirs[z+1];
                        if(nx<0 || nx>=m || ny<0 || ny>=n) continue;
                        int id = nx*n + ny;
                        if(st[id] == '0') st[id] = '1';
                        else st[id] = '0';
                    }
                    if(st == end) return res;
                    if(!mp.count(st)) {
                        q.push(st);
                        mp[st] = 1;
                    }
                }
            }
        }
        return -1;
    }
};