Minimum number of lasers required to cover cells in grid?

Question

I was asked this in an interview. I am modifying the question a bit to preserve it from being explicitly Googleable but the gist is:

You are given an N x M grid. Some cells in the grid are "evil" (denoted by number 1) and rest are "good" (denoted by 0). You have lasers positioned across each N rows and across each M columns which when turned on kills all cells in their respective row or column e.g. if you have:

   L1 L2 L3 L4
L5  0  1  0  0
L6  0  1  0  1
L7  0  1  1  0
L8  0  0  0  0

You can turn on either (L2, L3, L4):

   L1 L2 L3 L4
L5  0  x  x  x
L6  0  x  x  x
L7  0  x  x  x
L8  0  x  x  x

Or you can turn on (L2, L6, L7):

   L1 L2 L3 L4
L5  0  x  0  0
L6  x  x  x  x
L7  x  x  x  x
L8  0  x  0  0

A set of lasers turned-on is called "GoodConfig" iff it kills all evil cells. Note you can always turn on all lasers along a row or column and kill everything and it would be "GoodConfig" but turning on lasers is expensive and killing good cells is bad.

1. What is the smallest size of "GoodConfig" i.e. least number of lasers we can turn on till kill all evil cells?

2. What is a "GoodConfig" that minimizes the number of good cells killed?

Answer 1

This problem can be reformulated into the minimum vertex cover problem on a bipartite graph.

Consider a graph: vertices are rows (one part) and columns (the other part). There is an edge between vertices row and col if and only if the corresponding cell (row, col) is evil.

Our problem is now to find a set of vertices having minimal possible size such that each edge (former cell) of our graph has at least one vertex in our set (row or column).

According to Koenig's Theorem, we can find the maximum matching in our bipartite graph and then mark exactly one vertex of each edge of the matching so that the resulting set of vertices covers the graph in the above sense. In particular, the size of the maximum matching is equal to the size of the minimum vertex cover.

Answer 2

In order to answer to both 1) and 2), I would go with the following approach, assuming N or M are small (say <= 25).

Brute force on the set of rows/columns (whichever is smaller) selected and check the corresponding cost adding columns/rows to cover everything.

Lets say N <= M, there are 2^N sets of rows and we process the whole matrix for each one of them. This approach runs in O(2^N * N * M).

#define CONTAINS(mask, bit) (mask & (1 << bit))

void Solve(int matrix[MAX][MAX], int N, int M) {
    vector<int> best;
    int i, j, best_good_cells;
    for (int rows_mask = 0; rows_mask < (1 << N); rows_mask++) {
        vector<int> lasers;
        int good_cells = 0;
        for (j = 0; j < M; j++) {
            bool add_column = false;
            int good = 0;
            for (i = 0; i < N; i++)
                if (!CONTAINS(rows_mask, i)) {
                    if (matrix[i][j] == 0)
                        good++;
                    else
                        add_column = true;
                }
            if (add_column) {
                lasers.push_back(j);
                good_cells += good;
            }
        }
        for (i = 0; i < N; i++)
            if (CONTAINS(rows_mask, i))
                lasers.push_back(M+i);
        if (best.size() == 0 ||
                best.size() > lasers.size() ||
                (best.size()==lasers.size() && good_cells < best_good_cells)){
            best = lasers;
            best_good_cells = good_cells;
        }
    }
    cout << "Select lasers:";
    for (auto i: best)
        cout << " " << i+1;
    cout << endl;
}