营救公主.docx

【广度优先遍历】营救公主
分类: C程序 算法2013-07-20 20:48 191人阅读 评论(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] view plaincopy
<span style="font-family:Courier New;">#ifndef SAVE_PRINCESS_H  
#define SAVE_PRINCESS_H  
  
/* 
 * 公主被魔王抓走了,王子需要拯救出美丽的公主。他进入了魔王的城堡,魔王的城堡是一座很大的迷宫。 
 * 为了使问题简单化,我们假设这个迷宫是一个N*M的二维方格。迷宫里有一些墙,王子不能通过。王子只 
 * 能移动到相邻(上下左右四个方向)的方格内,并且一秒只能移动一步,就是说,如果王子在(x,y)一步 
 * 只能移动到(x-1,y),(x+1,y),(x,y-1),(x,y+1)其中的一个位置上。地图由‘S’,‘P’,‘.’,‘*’ 
 * 四种符号构成,‘.’表示王子可以通过,‘*’表示墙,王子不能通过;'S'表示王子的位置;‘P’表示公主 
 * 的位置;T表示公主存活的剩余时间,王子必须在T秒内到达公主的位置,才能救活公主。如下图所示: 
 */  
  
/* M行N列迷宫  
 * 如果能够救则返回1, 否则返回0 
 */  
extern int save_princess(int M, int N, char* maze_data, int time);  
  
#endif</span>  
[cpp] view plaincopy
<span style="font-family:Courier New;">#include ""  
#include <>  
#include <>  
#include <>  
  
enum DIRECTION  
{  
    D_UP = 0,  
    D_DOWN,  
    D_LEFT,  
    D_RIGHT,  
    D_SIZE  
};  
  
enum ROOM_TYPE  
{  
    TYPE_ROAD,  
    TYPE_WINDOW,  
    TYPE_PRINCE,  
    TYPE_PRINCESS,  
};  
  
struct room_info  
{  
    int row;  
    int col;  
    enum ROOM_TYPE type;  
    int pass_by;  
    struct room_info* child[D_SIZE];  
};  
  
static void init_room(struct room_info* r)  
{  
    memset(r, 0, sizeof(*r));