Minimum Number of Flips to Convert Binary Matrix to Zero Matrix solution and explanation

from collections import deque

class Solution:
    def minFlips(self, mat):
        def flip(bitmask, r, c):
            n, m = len(mat), len(mat[0])
            for i, j in [(r, c), (r+1, c), (r-1, c), (r, c+1), (r, c-1)]:
                if 0 <= i < n and 0 <= j < m:
                    bitmask ^= (1 << (i * m + j))
            return bitmask

        n, m = len(mat), len(mat[0])
        start = 0
        for i in range(n):
            for j in range(m):
                if mat[i][j]:
                    start |= (1 << (i * m + j))

        queue = deque([(start, 0)])
        visited = set()
        visited.add(start)

        while queue:
            bitmask, steps = queue.popleft()
            if bitmask == 0:
                return steps
            for i in range(n):
                for j in range(m):
                    next_bitmask = flip(bitmask, i, j)
                    if next_bitmask not in visited:
                        visited.add(next_bitmask)
                        queue.append((next_bitmask, steps + 1))

        return -1

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;

class Solution {
    private int flip(int bitmask, int r, int c, int n, int m) {
        for (int[] dir : new int[][]{{0, 0}, {1, 0}, {-1, 0}, {0, 1}, {0, -1}}) {
            int nr = r + dir[0], nc = c + dir[1];
            if (nr >= 0 && nr < n && nc >= 0 && nc < m) {
                bitmask ^= (1 << (nr * m + nc));
            }
        }
        return bitmask;
    }

    public int minFlips(int[][] mat) {
        int n = mat.length, m = mat[0].length;
        int start = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (mat[i][j] == 1) {
                    start |= (1 << (i * m + j));
                }
            }
        }

        Queue<int[]> queue = new LinkedList<>();
        HashSet<Integer> visited = new HashSet<>();
        queue.offer(new int[]{start, 0});
        visited.add(start);

        while (!queue.isEmpty()) {
            int[] node = queue.poll();
            int bitmask = node[0], steps = node[1];
            if (bitmask == 0) {
                return steps;
            }
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    int nextBitmask = flip(bitmask, i, j, n, m);
                    if (!visited.contains(nextBitmask)) {
                        visited.add(nextBitmask);
                        queue.offer(new int[]{nextBitmask, steps + 1});
                    }
                }
            }
        }
        return -1;
    }
}

from collections import deque

def min_flips(mat):
    m, n = len(mat), len(mat[0])

    def mat_to_bits(mat):
        bits = 0
        for i in range(m):
            for j in range(n):
                bits |= mat[i][j] << (i * n + j)
        return bits

    def bits_to_mat(bits):
        return [[(bits >> (i * n + j)) & 1 for j in range(n)] for i in range(m)]

    def flip(bit_map, i, j):
        directions = [(0, 0), (0, 1), (1, 0), (0, -1), (-1, 0)]
        for di, dj in directions:
            ni, nj = i + di, j + dj
            if 0 <= ni < m and 0 <= nj < n:
                bit_map ^= 1 << (ni * n + nj)
        return bit_map

    start = mat_to_bits(mat)
    if start == 0:
        return 0

    queue = deque([(start, 0)])
    visited = {start}

    while queue:
        state, step = queue.popleft()
        for i in range(m):
            for j in range(n):
                new_state = flip(state, i, j)
                if new_state == 0:
                    return step + 1
                if new_state not in visited:
                    visited.add(new_state)
                    queue.append((new_state, step + 1))

    return -1

#include <vector>
#include <queue>
#include <unordered_set>
using namespace std;

class Solution {
public:
    int minFlips(vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();

        auto matToBits = [&](const vector<vector<int>>& mat) {
            int bits = 0;
            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    bits |= (mat[i][j] << (i * n + j));
                }
            }
            return bits;
        };

        function<int(int,int)> flip = [&](int bits, int i, int j) {
            vector<pair<int, int>> directions = {{0, 0}, {0, 1}, {1, 0}, {0, -1}, {-1, 0}};
            for (auto& [di, dj] : directions) {
                int ni = i + di, nj = j + dj;
                if (0 <= ni && ni < m && 0 <= nj && nj < n) {
                    bits ^= 1 << (ni * n + nj);
                }
            }
            return bits;
        };

        int start = matToBits(mat);
        if (start == 0) return 0;

        queue<pair<int, int>> q;
        unordered_set<int> visited;
        q.emplace(start, 0);
        visited.insert(start);

        while (!q.empty()) {
            auto [state, step] = q.front();
            q.pop();
            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    int newState = flip(state, i, j);
                    if (newState == 0) return step + 1;
                    if (visited.insert(newState).second) {
                        q.emplace(newState, step + 1);
                    }
                }
            }
        }

        return -1;
    }
};

import java.util.HashSet;
import java.util.Set;

public class Solution {
    private final int[][] directions = {{0, 0}, {0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    public int minFlips(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        int start = matToBits(mat);
        if (start == 0) return 0;

        for (int depth = 1;; depth++) {
            if (dfs(start, 0, depth, new HashSet<>(), m, n)) {
                return depth;
            }
        }
    }

    private int matToBits(int[][] mat) {
        int m = mat.length, n = mat[0].length, bits = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                bits |= mat[i][j] << (i * n + j);
            }
        }
        return bits;
    }

    private int flip(int bits, int i, int j, int m, int n) {
        for (int[] d : directions) {
            int ni = i + d[0], nj = j + d[1];
            if (0 <= ni && ni < m && 0 <= nj && nj < n) {
                bits ^= (1 << (ni * n + nj));
            }
        }
        return bits;
    }

    private boolean dfs(int state, int depth, int maxDepth, Set<Integer> visited, int m, int n) {
        if (depth == maxDepth && state == 0) return true;
        if (depth < maxDepth) {
            visited.add(state);
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    int newState = flip(state, i, j, m, n);
                    if (!visited.contains(newState)) {
                        if (dfs(newState, depth + 1, maxDepth, visited, m, n)) {
                            return true;
                        }
                    }
                }
            }
            visited.remove(state);
        }
        return false;
    }
}

func minFlips(mat [][]int) int {
	m, n := len(mat), len(mat[0])
	state := 0
	for i, row := range mat {
		for j, v := range row {
			if v == 1 {
				state |= 1 << (i*n + j)
			}
		}
	}
	q := []int{state}
	vis := map[int]bool{state: true}
	ans := 0
	dirs := []int{0, -1, 0, 1, 0, 0}
	for len(q) > 0 {
		for t := len(q); t > 0; t-- {
			state = q[0]
			if state == 0 {
				return ans
			}
			q = q[1:]
			for i := 0; i < m; i++ {
				for j := 0; j < n; j++ {
					nxt := state
					for k := 0; k < 5; k++ {
						x, y := i+dirs[k], j+dirs[k+1]
						if x < 0 || x >= m || y < 0 || y >= n {
							continue
						}
						if (nxt & (1 << (x*n + y))) != 0 {
							nxt -= 1 << (x*n + y)
						} else {
							nxt |= 1 << (x*n + y)
						}
					}
					if !vis[nxt] {
						vis[nxt] = true
						q = append(q, nxt)
					}
				}
			}
		}
		ans++
	}
	return -1
}