2

我正在审查本地编程竞赛中的一个编程问题。

您可以下载问题http://www.vlaamseprogrammeerwedstrijd.be/2011/opgaves/cat2-2011/loodgieter.pdf。它是荷兰语，但图片将有助于理解它。

您收到 am*m 网格作为输入，其中包含一些管道和一些缺失点（问号）。其余的管道必须放置在网格中，以便它们与其他管道连接。

每个管道都用一个字母表示（参见第 2 页的图片）。字母“A”的值为 1，“B”的值为 2，...

有人知道如何通过在 Java 中回溯来解决这个问题吗？

4

1 回答 1

0

我建议收集你关于游戏的所有知识：

  • 边界更新连接
  • 管道相互连接
  • ? 我不太懂荷兰语；）

选择一个描述拼图的表示，在每个单元格中都有所需的连接（由已放置的部分暗示），并且可以是一些可能是也可能不是连接的选项

编写放置处理程序，当一块被放入棋盘时更新这些属性

创建决定零件是否可以放置在特定位置的逻辑。

此时从一个空板开始，放置你知道的部分

开始执行以下操作的递归：

  • 选择第一个空单元格
    • 如果没有复制当前板输出（解决方案）
  • 对于每件可用的作品，它会尝试它是否适合
    • 如果有，放置它并重新调用它自己

我希望你把它放在一起，这是一个很好的谜题，注意我每天玩的：每日专家netwalk，它是一种类似的，可以使用那里的启发式，也可以应用于这个问题。

于 2012-07-16T21:31:12.493 回答