营救公主.docx

【广度优先遍历】营救公主分类:C程序算法2013-07-2020:48191人阅读评论(0)收藏举报营救公主广度优先遍历题目描述:公主被魔王抓走了,王子需要拯救出美丽的公主。他进入了魔王的城堡,魔王的城堡是一座很大的迷宫。为了使问题简单化,我们假设这个迷宫是一个N*M的二维方格。迷宫里有一些墙,王子不能通过。王子只能移动到相邻(上下左右四个方向)的方格内,并且一秒只能移动一步,就是说,如果王子在(x,y)一步只能移动到(x-1,y),(x+1,y),(x,y-1),(x,y+1)其中的一个位置上。地图由‘S’,‘P’,‘.’,‘*’四种符号构成,‘.’表示王子可以通过,‘*’表示墙,王子不能通过;'S'表示王子的位置;‘P’表示公主的位置;T表示公主存活的剩余时间,王子必须在T秒内到达公主的位置,才能救活公主。如下图所示:上面是一个5*5的迷宫,红色箭头标识的是从S到P的一条路径。这条路径是最短的一条。如果题目中给的T是5的话,那么就无法救出公主。解法:对于这个迷宫问题,广度优先遍历可以找到一条最短的路径。我们把S作为树的根节点,其上下左右的点为孩子节点,那么首先肯定是看看孩子节点里面是不是公主。如果都不是的话,那么就查看某个孩子节点的4个孩子节点是否是公主。这也就是广度优先遍历了。首先我们给每个格子编个号码。然后我们把它变成树看看:图没画完.......发现我举的例子有些问题,数据太大了。大致的树如上图所示,广度优先遍历,找到公主时看一下那时是第几层就就知道最短路径是几步了。那么,怎么维护这个层数呢?初始化时根的层数为0。遍历时,取出当前节点的层数,然后把所有孩子的层数设置为level+1,然后让所有孩子入队列。这样就可以知道找到公主时是第几层了。代码如下:[cpp]viewplaincopy1.<spanstyle="font-family:CourierNew;">#ifndefSAVE_PRINCESS_H2.#./*5.*公主被魔王抓走了,王子需要拯救出美丽的公主。他进入了魔王的城堡,魔王的城堡是一座很大的迷宫。6.*为了使问题简单化,我们假设这个迷宫是一个N*M的二维方格。迷宫里有一些墙,王子不能通过。王子只7.*能移动到相邻(上下左右四个方向)的方格内,并且一秒只能移动一步,就是说,如果王子在(x,y)一步8.*只能移动到(x-1,y),(x+1,y),(x,y-1),(x,y+1)其中的一个位置上。地图由‘S’,‘P’,‘.’,‘*’9.*四种符号构成,‘.’表示王子可以通过,‘*’表示墙,王子不能通过;'S'表示王子的位置;‘P’表示公主10.*的位置;T表示公主存活的剩余时间,王子必须在T秒内到达公主的位置,才能救活公主。如下图所示:11.*/./*M行N列迷宫14.*如果能够救则返回1,否则返回015.*/(intM,intN,char*maze_data,inttime);.#endif</span>[cpp]viewplaincopy1.<spanstyle="font-family:CourierNew;">#include""2.#include<>3.#include<>4.#include<>.{=0,,,,.};.{,,,,21.};.{;;;;*child[D_SIZE];30.};(structroom_info*r)33.{(r,0,sizeof(*r));35.}./*38.*返回指向孩子的指针,孩子为墙则返回NULL39.*M*N的迷宫,max_row=M-1,max_col=N-140.*/*get_child(structroom_info*maze,intmax_row,intmax_col,*cur_room,enumDIRECTIONdirect)43.{