SGU 101 Domino

题意

给你一堆骨牌,每张骨牌正反两面各有一个0~6范围内的数字,你要做的是确定一种骨牌的排列方式和骨牌的正反似的相邻的两个骨牌的面数字一样。

思路

这种链接多个物体,物体之间通过公共部分链接,这种题是可以转换成图论题做的。那么这个题应该怎么转换?
我们建立0~6这7个节点,每张骨牌就可以看作是链接骨牌上两个数的边,我们要做的就是找到一个路径使得我们可以“一笔”走过所有的边,其实这个叫欧拉通路。
关于欧拉通路,欧拉回路的更多细节,可以参看http://haha.school/guanyuoulahuiluheoulalujing/
找出欧拉回路的方法就是DFS,但是和以往不同的是我们把处理工作放在下一层返回之后做。同时本题还需要判断欧拉回路是否存在,如果不存在的话要输出无解。

代码

 

Leave a Reply

Scroll to top