Số lần lật bit tối thiểu để chuyển ma trận nhị phân thành ma trận không trong C++

Cho ma trận nhị phân mat kích thước m x n. Trong một bước, ta có thể chọn một ô và lật bit của ô đó cùng với 4 ô lân cận (nếu có). Tìm số bước tối thiểu để chuyển mat thành ma trận toàn 0. Trả về -1 nếu không có lời giải.

Ví dụ: đầu vào [[0,0],[0,1]], cần 3 bước.

Thuật toán giải

Sử dụng BFS trên không gian trạng thái. Mỗi trạng thái được mã hóa thành một số nguyên (bitmask) đại diện cho ma trận. Từ trạng thái ban đầu, thử lật từng ô và các ô lân cận, đẩy trạng thái mới vào hàng đợi nếu chưa thăm. Dừng khi gặp trạng thái toàn 0.

Các bước chính:

1. Mã hóa ma trận ban đầu thành số nguyên x (bit i*m+j ứng với mat[i][j]).
2. Khởi tạo mảng dp kích thước 2^(n*m) giá trị -1, dp[x] = 0.
3. Hàng đợi q chứa x.
4. Lặp BFS: lấy trạng thái current, nếu bằng 0 trả về dp[current].
5. Với mỗi ô (i,j), tạo trạng thái temp bằng cách XOR bit tại (i,j) và 4 hướng.
6. Nếu dp[temp] == -1, cập nhật và đẩy vào hàng đợi.
7. Trả về -1 nếu không tìm thấy.

Chương trình C++ minh họa

#include <bits/stdc++.h>
using namespace std;

int dir[4][2] = {{1,0}, {-1,0}, {0,-1}, {0,1}};

class Solution {
public:
    int minFlips(vector<vector<int>>& mat) {
        int n = mat.size();
        int m = mat[0].size();
        int x = 0;
        for(int i=0; i<n; i++)
            for(int j=0; j<m; j++)
                x += (mat[i][j] << ((i*m)+j));

        vector<int> dp(1 << (n*m), -1);
        dp[x] = 0;
        queue<int> q;
        q.push(x);

        while(!q.empty()) {
            int current = q.front(); q.pop();
            if(current == 0) return dp[current];
            for(int i=0; i<n; i++) {
                for(int j=0; j<m; j++) {
                    int temp = current;
                    temp ^= (1 << ((i*m)+j));
                    for(int k=0; k<4; k++) {
                        int ni = i + dir[k][0];
                        int nj = j + dir[k][1];
                        if(ni<0 || nj<0 || ni>=n || nj>=m) continue;
                        temp ^= (1 << ((ni*m)+nj));
                    }
                    if(dp[temp] == -1) {
                        dp[temp] = dp[current] + 1;
                        q.push(temp);
                    }
                }
            }
        }
        return -1;
    }
};

int main() {
    Solution ob;
    vector<vector<int>> v = {{0,0},{0,1}};
    cout << (ob.minFlips(v));
    return 0;
}

Kết quả

3