最近工作很忙,连写代码的时间也没有。呵呵,希望明天我能有时间实际试试。
这题确实类似于哈密尔顿路,但并不是,因为灰色格的存在。
还有比较质疑孔明估计的复杂度。O(n*m*2^n)由于n、m <= 10,所以这个估计的规模只有10万级,怎么做也不过几个毫秒的事。如果真有这样的算法我真想看看。
DFS的复杂度应该是O(C^nm)。这里的C介于1至4之间,我无法分析出准确的C值。
目前我只能从剪枝入手。简单分析一下可以得到这样的剪枝条件:
连线在任何一行上只能经过一种颜色的格子。也就是说如果连线已经在这行上经过了黑(白)格子就不能再进入这一行上的白(黑)格子。
在起点和终点所在的行只能经过这两点颜色的格子。
希望明天能试一下。其他朋友可以参考我的剪枝条件。如果试了请告诉我效果如何(我不一定有时间能自己写代码玩了)呵呵