我在示例中找不到模式

I can't find a pattern in the examples

我正在为一家公司的实习生职位工作,但我在理解部分情况本身方面遇到了一些问题。这个问题更侧重于解决问题的方式,而不是编写代码。代码不是问题。

条件的重要部分:

搭建者必须用两层大小为1×2的长方形砖块覆盖一个大小为 M×N( M和 N为偶数)的矩形区域。第一层砖已经完成。第二层(为了使砖砌体真正坚固)必须在其中没有砖块完全位于第一层的砖块上。但是,允许一半相同的砖块位于第二层的同一块砖块上。创建一个控制台应用程序,它接受第一层砖块给定布局的输入参数,确定第二层砖块的可能布局,或者证明不可能创建第二层并在控制台中打印它。

输入包含给出区域尺寸的行,接下来的行给出第一层的布局。

这些是第一层和预期的第二层的一些示例:

一个简单的例子

由更多积木组成的例子

我明白第二层的砖应该怎么放了,正如例子所示,砖的数量和放置方式是有逻辑和一致性的。下一个示例打破了我在这两个示例中发现的逻辑和一致性。

大面积积木

我的问题是: 你在数字中找到任何序列了吗?你认为它们只是砖块的某种“id”吗?

通过关注数字的模式,您已经很好地开始将问题 space 分解到尽可能小的领域。但是,也许您误解了域。也许问题不应该根据数字代表每块砖的方式来分解。

域的呈现方式似乎无法提供可以以简单的交叉影线图案铺设的均匀砖层。虽然这似乎是一个限制条件,但它可能正是关键要求。具体来说,

The second layer ( in an effort to make the brickwork really strong) must be created in away that no brick in it lies exactly on a brick from the first layer.

这是一个非常具体的要求,在问题定义中很容易被忽略,因为它被伪装成约束。如果将其视为一项要求,那么很明显,砖块不是寻找解决方案的地方。定义问题space.

是砖块的交集

知道了,图表非常清楚地显示了交叉点是如何定义的:交叉点存在于每 1/2 块砖上。这正是这个问题的创造者必须为每个砖块提供两个索引的原因。

鉴于:

  • 第二层砖不能覆盖第一层的砖
  • 每半块编号相同的砖块

:

二层铺砖

然后:

关于积木的重叠,下列任何一项都可能是正确的:

  • 二层号码匹配不依赖于一层号码匹配
  • 如果两层的数字相同,则只有一层二号匹配一层一号

重叠中不允许出现以下内容:

  • 第一层和第二层编号相同
  • 匹配二层号不在匹配一层号之上

这一切意味着:

  1. 有两个尺寸为 M×N 的笛卡尔平面
  2. 一个覆盖另一个
  3. 将输入数字放在 M×N 维的网格上

问题解决:

将第二层数字放在上面的网格上,这样相同的数字在任一方向上都彼此相邻(1,1;2,2;等),而上面没有两个匹配的数字位于相同的网格位置以下匹配号码。

如果你推导的算法不能达到那个目标,那么它就是一个不可能的网格。

希望对您有所帮助。