对于给定的一张N*M(1 <= N,M <= 12)棋盘，求经过所有格子的哈密顿回路的个数。如下图所示，红色部分为不能经过的格子，绿色线条即为一个合法的方案。
注:算法时间限制(1s),若无人可解,本人讲发布题解网址(非广告)

[ 本帖最后由 a351357741 于 2010-9-28 22:05 编辑 ]

可以试下！呵呵，不过需要时间的！

支持!

有无测试数据？？LZ顺便一起贴出来吧！！我计划用下面的思路来处理：

哈密顿回路  

经过图（有向图或无向图）中所有顶点一次且仅一次的通路称为哈密顿通路。经过图中所有顶点一次且仅一次的回路称为哈密顿回路。具有哈密顿回路的图称为哈密顿图，具有哈密顿通路但不具有哈密顿回路的图称为半哈密顿图。平凡图是哈密顿图。 

一种简单的哈密顿环寻找方法
哈密顿回路又称哈密顿环，有名的“环游世界问题”指的就是寻找哈密顿环问题。据说，该问题是一个NP完全问题。但下面有一种简单的哈密顿环寻找方法，可以提供参考：

假设有一个图G，图中不存在交叉线（即如果有交叉线就认为交叉点也是图的一个顶点），以图G中任取的一个环T(即除了与环中相邻的顶点有连接外，与其他属于该环的顶点无连接)为起点，逐步扩展该环的范围，直到图G的所有顶点都在环中为止,此时所得的环一定是哈密顿环。扩展规则为：

　　任取环T的一边，如果该边不是图G最外围的边且去除该边后不会导致环的断裂（即不产生某个顶点只有一条边与其相连的情况），就将其去除。由此产生一个更大的环，以该环为新的选择，重复上面的去边操作，直到图G的所有顶点都在环上或者去除环的任何一边再也不会导致环的扩大，如果是前一种情况，则表明找到了一个哈密顿环，否则该图不存在哈密顿环。

PS：
分数不是个问题！呵呵，我只是想看下能否自己写代码解决这样的问题！

[ 本帖最后由 jack10141 于 2010-9-28 22:39 编辑 ]

其实楼上的jack10141你知道DP为何物不？只是提醒你一下，我发现你之前发的代码都没有运用到DP的思路，只是纯解题，在复杂度上没有多大的优化

如你所说，我还真的不知道DP为何物，但是我至少有baidu可以请教，呵呵！
此题的规模不大，没有完全运用到DP的思路，我想也是可以达到题目1s的要求的！

你得看是什么题了，这句话不是什么都能套的

动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象前面所述的那些搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此读者在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。我们也可以通过对若干有代表性的问题的动态规划算法进行分析、讨论，逐渐学会并掌握这一设计方法。

Sample Input
4 4
**..
....
....
....
Sample Output
2