[POJ 1872]

A Dicey Problem

广搜

题意:有一个最大10*10的格盘,上面有一个标准色子。规定如果色子朝上的一面和相邻的某盘格的数字相同,或者盘格数字为-1,那么色子可以朝该方向滚动一格。问是否存在一条路径,使色子在格盘上从初始位置出发后,还能回到初始位置。若有解则数据保证只有唯一解。最后还要输出滚动方案。

这是1999年World Finals的C题……读完题面后很容易发现数据规模不大,状态转移不多,不需要特别优化。相比起来,需要花费更多时间考虑的是数据结构的表示。

色子有6面,但其姿态可以由正面和顶面两个数字来唯一确定,总共有6*4=24种可能。盘面最多100个格子,因此搜索空间是2400。可以将盘面状态表示为:((正面值-1)*6+(顶点值-1))*100+(纵坐标-1)*10+(横坐标-1)。当从队列中取出一个状态时,先由正面和顶点值得到整个色子当前6个面的值,这里可以将6个面分别编号,然后按六进制的方式(或者每个数用3位表示,移位处理)压成一个整型,再打表处理。然后模拟4个方向的滚动,求6个面的新值,再判断在该方向上的盘面值是否允许滚动。当回到原点时,返回当前状态以便回溯输出解方案。

一开始考虑时,直接用了全部六个面的值和坐标来作为状态,这样d和p数组的大小都是6^6*10*10=4665600,正常来说这也不是一个太大的值。但是这题test cases非常多。每次都memset的话,就超时了。因此只能在不丢失信息的情况下尽量压缩状态。