广度优先搜索算法（Breadth-FirstSearch），又称为"宽度优先搜索"或"横向优先搜索"主要可以解决两类问题：
·是否存在从起点到终点的路径
·找出从起点到终点的最短路径a
算法描述:
1intbfs(){2初始化首结点入队（首指针为0，尾指针为1）3while(首指针小于尾指针){4首指针后移一位5for(;;){产生子结点6if(){判断子结点是否满足条件7if(){如果结点未与之前产生过重复8尾指针后移9存入新的结点（提供结点的父结点和层数）10if(){如果新结点是目标节点11输出并退出12}13}14}15}16}17}
值得注意的是，广搜的过程中每生成一个子结点，都要提供指向他们的父结点的指针和层数，以免找到解的时候找不到来时的路径。
广度优先搜索在访问完该层的所有结点后，才开始访问下一层
关于从搜索树通过队列存入数组的思想：
八字码问题
Description
The15-puzzlehasbeenaroundforover100years;evenifyoudon'tknowitbythatname,you'veseenit.Itisconstructedwith15slidingtiles,eachwithanumberfrom1to15onit,andallpackedintoa4by4framewithonetilemissing.Let'scallthemissingtile'x';theobjectofthepuzzleistoarrangethetilessothattheyareorderedas:
123456789101112131415x
wheretheonlylegaloperationistoexchange'x'withoneofthetileswithwhichitsharesanedge.Asanexample,thefollowingsequenceofmovessolvesaslightlyscrambledpuzzle:
123412341234123456785678567856789x1012910x129101112910111213141115131411151314x15131415xr->d->r->
Thelettersinthepreviousrowindicatewhichneighborofthe'x'tileisswappedwiththe'x'tileateachstep;legalvaluesare'r','l','u'and'd',forright,left,up,anddown,respectively.Notallpuzzlescanbesolved;in1870,amannamedSamLoydwasfamousfordistributinganunsolvableversionofthepuzzle,andfrustratingmanypeople.Infact,allyouhavetodotomakearegularpuzzleintoanunsolvableoneistoswaptwotiles(notcountingthemissing'x'tile,ofcourse).Inthisproblem,youwillwriteaprogramforsolvingthelesswell-known8-puzzle,composedoftilesonathreebythreearrangement.
Input
Youwillreceiveadescriptionofaconfigurationofthe8puzzle.Thedescriptionisjustalistofthetilesintheirinitialpositions,withtherowslistedfromtoptobottom,andthetileslistedfromlefttorightwithinarow,wherethetilesarerepresentedbynumbers1to8,plus'x'.Forexample,thispuzzle
123x46758
isdescribedbythislist:
Output
Youwillprinttostandardoutputeithertheword``unsolvable'',ifthepuzzlehasnosolution,orastringconsistingentirelyoftheletters'r','l','u'and'd'thatdescribesaseriesofmovesthatproduceasolution.Thestringshouldincludenospacesandstartatthebeginningoftheline.
SampleInput
23415x768
SampleOutput
ullddrurdllurdr
这道题的思路大概是这样子
1.读入到a数组内2.输出一下a数组做一个子程序print23.定义一下宽搜的节点1）首先有一个a棋盘（是一个二维数组）2）移动空位，记住空位的位置x，y3)记录深度（你走了几步)叫dep4）父节点，打方案用，走法dd4.定义队列大数组结构体data1100000一个头指针op，尾指针cl5.偏移量，空位的移动方案d[5]结构体d[1].xd[1].y偏移6.初始化队列首节点入队（初始状态）写一个拷贝子程序7.做一个棋盘之间的复制copy(a,b)把a棋盘的值拷贝到b棋盘8.判断两个棋盘的值是否相同
9.判断队列中棋盘是否存在exist(a)a棋盘在我的data1数组中从1到cl是否存在10.输出方案的子程序print111.写宽搜的框架
但这个时候问题来了，单项搜索的效率太低了！！！如果要走20步，程序需要运行8秒多！！！
这个时候，我们会发现题目中给出了终态！在这种情况下，同样的搜索从初态和终态出发各搜索一半状态，产生两棵深度减半的搜索树，在中间交会、组合成最终的答案。
这道题是不是完美地解决了？？
等等！还有unsolvable的判断！但是这道题不能用搜索来判断是否有解------无解的时候程序将无限的搜索下去！！
这个时候就需要事先判断八个数字的排列了。
我们会用到置换：
（摘自百度百科）
也就是说，我们可以统计排列中逆序的次数（即后一项小于前一项，0不计），如果有奇数次，则无解。