要求激光器的最小数量的覆盖单元网格？ [英] Minimum number of lasers required to cover cells in grid?

问题描述

我是在一次采访中问这个。我有点为preserve它被明确Googleable修改的问题，但要点是：

您将得到一个 N×M个网​​格。有些细胞在网格中的恶（记为1号）和其余是好（记为0）。你有激光定位在每个 N 行和跨越，当在各自的行击杀打开所有的单元，每个单元 M 列或列如：如果您有：

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

您可以打开或者（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
 

或者你可以打开（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
 

一组激光开启的被称为GoodConfig当且仅当它杀死所有的邪恶细胞。注意：您可以随时打开沿行或列中的所有激光器并杀死一切，这将是GoodConfig，但打开激光器价格昂贵，杀好细胞是坏的。

1. 什么是GoodConfig，即最少数量的激光器的尺寸最小，我们可以打开，直到杀死所有邪恶的细胞？

2. 什么是GoodConfig，最大限度地减少对杀好细胞的数量？

解决方案

这个问题可以重新插入一个二分图的最小顶点覆盖问题。

考虑的曲线图：顶点的行（1份）和列（其它部分）。有顶点行和 COL 当且仅当相应的单元格（行之间的边缘，COL）是邪恶的。

我们的问题是现在发现了一组具有最小可能的尺寸的顶点，使得我们的图的每条边（前小区）在我们的组（行​​或列）中的至少一个顶点。

根据柯尼希定理，我们可以发现，在最大匹配我们二部图，然后标记的匹配的每个边缘的恰好一个顶点，使得所得顶点集合覆盖所述图形在上述感。特别是，最大匹配的尺寸是等于最小顶点覆盖的大小。

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?

解决方案

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.

这篇关于要求激光器的最小数量的覆盖单元网格？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！