Lật ngẫu nhiên ma trận nhị phân (Random Flip Matrix) trong C++

Ma trận n_rows x n_cols toàn 0. Hàm flip() chọn ngẫu nhiên một ô 0, đặt thành 1, trả về tọa độ. Hàm reset() đặt lại toàn 0. Tối ưu hóa số lần gọi random.

Thuật toán (Mapping + Fisher-Yates idea)

1. Tổng ô size = n*m. Map holes lưu mapping cho các ô đã flip.
2. flip(): random id trong [0, size-1], giảm size. Nếu id trong holes lấy giá trị thật. Cập nhật holes[old_id] = holes[size] hoặc size. Trả về (id/m, id%m).
3. reset(): khôi phục size, xóa holes.

Mã nguồn C++

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

class Solution {
    unordered_map holes;
    int n, m, size;
public:
    Solution(int n_rows, int n_cols) : n(n_rows), m(n_cols), size(n_rows*n_cols) {
        srand(time(NULL));
    }
    vector flip() {
        int id = rand() % size;
        size--;
        int rid = id;
        if (holes.count(id)) id = holes[id];
        holes[rid] = holes.count(size) ? holes[size] : size;
        return {id / m, id % m};
    }
    void reset() {
        size = n * m;
        holes.clear();
    }
};

Ví dụ

Ma trận 2x2, flip 4 lần → trả về 4 tọa độ khác nhau.