algorithm - 多米诺骨牌 - 比赛

Question

http://ecoocs.org/contests/ecoo_2007.pdf

我正在为我所在地区即将举行的 ecoo regionals 学习，但我对这个问题感到困惑。我真的不知道从哪里开始。

它在“区域”“西部和中部”部分“问题 3 - 多米诺骨牌链”。

我一直在手动解决这个问题，我一直在考虑广度优先搜索或深度优先搜索，但是有两个面的多米诺骨牌严重打乱了我的想法。有没有人有任何建议或一些资源可以让我朝着正确的方向前进？

Answer 1

看起来这个问题需要递归回溯方法。保留一个 7 x 7 对称矩阵，显示哪些数字附加到哪些。例如，给定瓷砖 00 12 63 51 您将拥有以下矩阵:

  0 1 2 3 4 5 6 
  -------------
0|1 0 0 0 0 0 0
1|0 0 1 0 0 1 0
2|1 0 0 0 0 0 0
3|0 0 0 0 0 0 1
4|0 0 0 0 0 0 0
5|0 1 0 0 0 0 0
6|0 0 0 1 0 0 0

当您通过将图 block 放置在潜在链中用完它时，将其从矩阵中删除，并在通过回溯取消放置图 block 后将其放回矩阵中。例如，如果链当前包含 51 12，则矩阵如下所示:

  0 1 2 3 4 5 6 
  -------------
0|1 0 0 0 0 0 0
1|0 0 0 0 0 0 0
2|0 0 0 0 0 0 0
3|0 0 0 0 0 0 1
4|0 0 0 0 0 0 0
5|0 0 0 0 0 0 0
6|0 0 0 1 0 0 0

鉴于链当前以 2 结尾，您将沿着第 2 行查找可以连接的任何数字。如果找不到，您可以将 51 12 标记为可能最长的链，然后回溯到该链仅包含 51 的状态。

维护一个你发现的所有最长链的集合，并在插入之前检查一个新链是否存在于该集合中或其反向链。

如果您发现一条较长的链条，请开始一个新的链条。彻底搜索所有可能的链后，集合的大小应该是长度最长的变体数量。