sgu做到290道了,这个月的目标也算达成了。
这道题就是骑士遍历问题:给定n*n的棋盘,从任意一点出发,按马的规则,求一条遍历棋盘的路径。本质上这是个哈密尔顿路,因为在棋盘上有很多优化的方法。这道题其实也算是论文题,如果知道Warnsdorff’s rule的话就很容易了。如果知道这个启发式规则还不能ac就是在度数相同的点中处理的先后顺序的排法上乱搞,或者继续找论文。我是把输入分成2类,一类是坐标和小的排在前能出解,一类是坐标和大的排在前能出解。
最后推荐一篇论文"
A METHOD FOR FINDING HAMILTON PATHS AND KNIGHT’S TOURS",这个在ACM的数据库中就能查到……