Đếm số phép toán chuyển ma trận nhị phân thành ma trận toàn 0 trong C++

Cho một ma trận nhị phân. Xét phép toán: chọn một ô và lật nó cùng các ô lân cận (lên, xuống, trái, phải). Tìm số phép toán tối thiểu để ma trận chỉ chứa 0. Nếu không có lời giải, trả về -1.

Ví dụ đầu vào:

0	0
1	0

Đầu ra: 3.

Phương pháp giải

Sử dụng BFS trên không gian trạng thái (bitmask). Các bước:

Mảng hướng dir[4][2] = {{1,0},{0,1},{-1,0},{0,-1}}
Hàm getPos(i, j) trả về i * c + j
Hàm getCoord(x) trả về cặp (x/c, x%c)
Chuyển ma trận thành bitmask mask
Mảng dist[512] lưu khoảng cách, khởi tạo -1
Queue BFS từ mask, dist[mask] = 0


Khi pop mask: thử lật từng ô i (0 đến last-1), tính nmask bằng XOR bit i và 4 hướng lân cận hợp lệ
Nếu dist[nmask] == -1 hoặc dist[nmask] > dist[mask] + 1: cập nhật và push
Trả về dist[0] (trạng thái toàn 0)



Chương trình minh họa
#include <bits/stdc++.h>
using namespace std;

int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int c, r, last;
const int INF = 1e6;

int getPos(int i, int j) {
    return i * c + j;
}

pair<int, int> getCoord(int x) {
    return {x / c, x % c};
}

int solve(vector<vector<int>>& matrix) {
    int mask = 0;
    r = matrix.size();
    c = r ? matrix[0].size() : 0;
    last = r * c;
    
    for (int i = 0; i < r; i++)
        for (int j = 0; j < c; j++)
            mask ^= (matrix[i][j] << getPos(i, j));
    
    vector<int> dist(1 << 9, -1);
    queue<int> q;
    q.push(mask);
    dist[mask] = 0;
    
    while (!q.empty()) {
        mask = q.front();
        q.pop();
        
        for (int i = 0; i < last; i++) {
            auto coord = getCoord(i);
            int x = coord.first;
            int y = coord.second;
            int nmask = mask;
            nmask ^= (1 << i);
            
            for (int k = 0; k < 4; k++) {
                int nx = x + dir[k][0];
                int ny = y + dir[k][1];
                if (nx < 0 || nx >= r || ny < 0 || ny >= c)
                    continue;
                int pos = getPos(nx, ny);
                nmask ^= (1 << pos);
            }
            
            if (dist[nmask] == -1 || dist[nmask] > dist[mask] + 1) {
                dist[nmask] = dist[mask] + 1;
                q.push(nmask);
            }
        }
    }
    return dist[0];
}

int main() {
    vector<vector<int>> v = {{0, 0}, {1, 0}};
    cout << solve(v);
    return 0;
}


Đầu vào
{{0, 0}, {1, 0}}


Đầu ra
3