algorithm - 将线拟合到网格矩阵中 [竞争，不是硬件]

Question

在最近由“AmDocs”组织的比赛中，我遇到了以下问题：（问题的基本思想）

给定一个固定大小为 12x12 的矩阵。给你六个长度为 6,5,5,4,3,2 的线段。矩阵有空格和填充空格。您必须返回 "Yes" 或 "No" ，是否所有 6 条线段都可以同时适合矩阵。线条只能水平或垂直放置。

应该使用什么算法来解决这个问题？包装 ？背包？

Answer 1

我会将问题映射到 SAT 并使用 SAT 求解器。有一个非常自然的映射。定义变量：

x_s_i_j_d = segment s starts at coordinates (i,j) and goes in direction d

（d 是“右”或“下”）

首先，遍历所有的段和起始位置，看看在给定起始矩阵的情况下哪些是可行的。例如，米：

000000000000
111111111111
...

如果段 1 的长度为 2，则L_seg1_0_0_down = false，因为它遇到了一个填充的空间。

然后，编写禁止两个交叉段的子句。如果段 1 和段 2 的长度都是 2，那么我们添加子句：

(!L_seg1_0_0_right || !L_seg2_1_0_right)

因为如果段 1 使用坐标 (0,0) 和 (1,0)，则段 2 也不能使用 (1,0)。

最后，添加每个段必须至少使用一次的条件：

(L_seg1_0_0_right || L_seg1_0_1_right || ...)

对于 seg1 可以去的所有位置。然后把你最​​喜欢的 SAT 求解器扔给它。

Answer 2

我会使用如下贪婪填充算法：

for largest_line to smallest_line do
  for first_empty_square_in_matrix to last_empty_square_in_matrix do
    if line_fits_horizontal then
      place_line
      break
    else if_line_fits_vertical then
      place_line
      break
if all_lines_placed then
  write('Yes')
else
  write('No')

为了优化上述内容，您可能会注意到，如果长度为 n 的水平线无法适合位置 (i,j)，那么您将不需要测试它是否水平适合 (i+1,j),(i +2,j)...(i+n,j)。

Answer 3

只是一个想法：
遍历所有 2D 数组点并创建可用段的集合。在每个步骤中，您将分析 i-1 和 j-1 单元格，如果您有包含该单元格的段，您将增加它们的长度（显然您最多可以找到两个段）。
之后，您应该将数组放入可用的段中，因此在每次插入后，您应该分析所有剩余的段，如果它们中的任何一个与当前插入的段相交，您应该减小它们的大小或分成两个。