这道题WA了好几天了,总是不知道哪里出了问题,后来看了看,到处都是问题. …… 本来想开始复习考试科目的,奈何总是受这道未A的题目的干扰,总算是解决了。
题意
给你棋盘的初始状态和结束状态,问你从初始状态到结束状态能不能只通过不多于八步的移动。
思路
如果是单向BFS,每次移动有16种可能,8步就是$16^8$ ,还是很大的。不过通过剪枝还是能过的。
但是双向BFS,简单写写就过了,前提是你得会啊QWQ
存储状态用的八维数组,找个时间用hash存储状态。
提醒几点我出错的地方。排序的时候忘记加引用,跳完两步之后,可能那个位置本身也有棋子,注意将状态Push进队列的顺序,是在判断完那几个if之后。记得vis要用char或者bool类型,否则会MLE。
本来已经总结了类似的模板,结果看了网上的题解,不断的修改模板,最后又改回了我的原本的模板。兜兜转转,人生如此QWQ。。
不得不说,双向BFS真快啊!
1 |
|