学步园

题目描述：

公主被魔王抓走了，王子需要拯救出美丽的公主。他进入了魔王的城堡，魔王的城堡是一座很大的迷宫。为了使问题简单化，我们假设这个迷宫是一个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，然后让所有孩子入队列。这样就可以知道找到公主时是第几层了。

代码如下：

#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

#include "save_princess.h"
#include <string.h>
#include <stdlib.h>
#include <stdio.h>

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));
}

/* 
 * 返回指向孩子的指针,孩子为墙则返回NULL
 * M*N 的迷宫，max_row = M - 1, max_col = N - 1
 */
static struct room_info* get_child(struct room_info* maze, int max_row, int max_col, 
					   struct room_info* cur_room, enum DIRECTION direct)
{
	int row = 0;
	int col = 0;
	int idx = 0;
	struct room_info* child = NULL;

	if (NULL == maze
		|| NULL == cur_room)
	{
		return NULL;
	}
	
	row = cur_room->row;
	col = cur_room->col;

	switch (direct)
	{
	case D_UP:
		if (row <= 0)
		{
			return NULL;
		}

		row--;
		break;
	case D_DOWN:
		if (row >= max_row)
		{
			return NULL;
		}
		row++;

		break;
	case D_LEFT:
		if (col <= 0)
		{
			return NULL;
		}
		col--;

		break;
	case D_RIGHT:
		if (col >= max_col)
		{
			return NULL;
		}
		col++;

		break;
	default:
		break;
	}

	idx = row * (max_col + 1) + col;

	child = maze + idx;
	if (TYPE_WINDOW == child->type)
	{
		return NULL;
	}
	else
	{
		return child;
	}
}

/* 成功返回指向S的指针， 失败返回NULL*/
static struct room_info* init_maze(struct room_info* maze, int M, int N, char* maze_data)
{
	int row = 0;
	int col = 0;
	struct room_info* prince = NULL;

	/* 第一遍识别墙等,确定坐标 */
	for (row = 0; row < M; row++)
	{
		for (col = 0; col < N; col++)
		{
			int idx = row * N + col;
			char c = *(maze_data + idx);

			init_room(maze + idx);

			maze[idx].row = row;
			maze[idx].col = col;

			switch (c)
			{
			case '.':
				maze[idx].type = TYPE_ROAD;
				break;
			case '*':
				maze[idx].type = TYPE_WINDOW;
				break;
			case 'S':
				prince = maze + idx;
				maze[idx].type = TYPE_PRINCE;
				break;
			case 'P':
				maze[idx].type = TYPE_PRINCESS;
				break;
			default:
				return NULL;
			}
		}
	}

	/*第二遍建立图*/
	for (row = 0; row < M; row++)
	{
		for (col = 0; col < N; col++)
		{
			int idx = row * N + col;

			maze[idx].child[D_UP]	= get_child(maze, M - 1, N - 1, maze + idx, D_UP);
			maze[idx].child[D_DOWN]	= get_child(maze, M - 1, N - 1, maze + idx, D_DOWN);
			maze[idx].child[D_LEFT]	= get_child(maze, M - 1, N - 1, maze + idx, D_LEFT);
			maze[idx].child[D_RIGHT]= get_child(maze, M - 1, N - 1, maze + idx, D_RIGHT);
		}
	}

	return prince;
}

struct node_info
{
	int level;
	struct room_info* room;
	struct node_info* parent;

	struct node_info* next;
};

static void init_node_info(struct node_info* info)
{
	memset(info, 0, sizeof(*info));
}

static void queue_push(struct node_info* queue, 
						struct room_info* room, 
						int cur_level, 
						struct node_info* parent)
{
	struct node_info* new_node = NULL;

	if (NULL == room)
	{
		return;
	}

	new_node = (struct node_info*)malloc(sizeof(struct node_info));
	init_node_info(new_node);
	
	new_node->level = cur_level + 1;
	new_node->parent = parent;
	new_node->room = room;

	while (queue != NULL)
	{
		if (NULL == queue->next)
		{
			queue->next = new_node;
			break;
		}

		queue = queue->next;
	}
}

static void queue_release(struct node_info* queue)
{
	struct node_info* tmp = NULL;
	while (queue != NULL)
	{
		tmp = queue->next;
		free(queue);
		
		queue = tmp;
	}
}

/* 找到princess返回需要的步数
 * 找不到或者出错返回-1
 */
static int find_princess(struct room_info* maze, struct room_info* prince)
{
	struct node_info* queue =  NULL;
	struct node_info* cur_step =  NULL;

	queue = (struct node_info*)malloc(sizeof(struct node_info));
	if (NULL == queue)
	{
		return -1;
	}

	init_node_info(queue);
	queue->parent = NULL;
	queue->level = 0;
	queue->room = prince;

	cur_step = queue;
	while (cur_step != NULL)
	{
		struct room_info* cur_room = cur_step->room;
		if (NULL == cur_room)
		{
			fprintf(stderr, "IT CAN NOT HAPPEN!\n");
			break;
		}

		if (TYPE_PRINCESS == cur_room->type)
		{
			struct node_info* tmp = cur_step;
			/* we find princess   */
			fprintf(stdout, "\nThe way back to prince... \n");
			while (tmp != NULL)
			{
				fprintf(stdout, "(%d, %d) ", tmp->room->row, tmp->room->col);

				tmp = tmp->parent;
			}
			fprintf(stdout, "\n");

			queue_release(queue);
			return cur_step->level;
		}
		else if (TYPE_ROAD == cur_room->type
			    || TYPE_PRINCE == cur_room->type)
		{
			struct room_info* tmp = NULL;

			if (1 == cur_room->pass_by)
			{
				cur_step = cur_step->next;
				continue;
			}

			cur_room->pass_by = 1;

			/* 把孩子们丢到队列后面 */
			tmp = cur_room->child[D_UP];
			queue_push(queue, tmp, cur_step->level, cur_step);

			tmp = cur_room->child[D_DOWN];
			queue_push(queue, tmp, cur_step->level, cur_step);

			tmp = cur_room->child[D_LEFT];
			queue_push(queue, tmp, cur_step->level, cur_step);

			tmp = cur_room->child[D_RIGHT];
			queue_push(queue, tmp, cur_step->level, cur_step);
		}
		else 
		{
			fprintf(stderr, "Wired!\n");
		}

		cur_step = cur_step->next;
	}

	queue_release(queue);
	return -1;
}

int save_princess(int M, int N, char* maze_data, int time)
{
	struct room_info* maze = NULL;
	struct room_info* prince = NULL;
	int time_need = 0;

	if (M <= 1
		|| N <= 1
		|| NULL == maze_data
		|| 0 == time)
	{
		return 0;
	}

	maze = (struct room_info*)malloc(M * N * sizeof(struct room_info));
	if (NULL == maze)
	{
		return 0;
	}

	prince = init_maze(maze, M, N, maze_data);
	if (NULL == prince)
	{
		/*输入数据有误*/
		return 0;
	}

	time_need = find_princess(maze, prince);
	if (-1 == time_need)
	{
		return 0;
	}
	else if (time_need > time)
	{
		return 0;
	}
	else
	{
		return 1;
	}
}

#include "save_princess.h"
#include <stdio.h>

#define M 10
#define N 10

int main()
{
	int ret = 0;
	int row = 0;
	int col = 0;

	char maze_info[M][N] = {\
	/*      0    1    2    3    4    5    6    7    8    9*/
	/*0*/ {'.', '.', '.', '*', '.', '.', '.', '.', '.', '.'},
	/*1*/ {'.', 'S', '*', '.', '.', '.', '.', '.', '.', '.'},
	/*2*/ {'.', '.', '*', '.', '.', '.', '.', '.', '.', '.'},
	/*3*/ {'.', '.', '*', '*', '.', '*', '.', '.', '.', '.'},
	/*4*/ {'.', '.', '.', '*', '.', '*', '.', '.', '.', '.'},
	/*5*/ {'.', '.', '.', '*', '.', '.', '.', '.', '.', '.'},
	/*6*/ {'.', '.', '*', '.', '.', '.', '.', '.', '.', '.'},
	/*7*/ {'.', '.', '*', '.', '*', '.', '*', '.', '.', '.'},
	/*8*/ {'.', '.', '.', '.', '*', '.', '*', '*', '*', '.'},
	/*9*/ {'.', '.', '*', '.', '*', '.', '*', 'P', '.', '.'}};

	fprintf(stdout, "\n  ");
	for (col = 0; col < N; col++)
	{
		fprintf(stdout, "%d ", col);
	}
	fprintf(stdout, "\n");

	for (row = 0; row < M; row++)
	{
		fprintf(stdout, "%d ", row);
		for (col = 0; col < N; col++)
		{
			fprintf(stdout, "%c ", maze_info[row][col]);
		}
		fprintf(stdout, "\n");
	}

	ret = save_princess(M, N, (char*)maze_info, 6);

	fprintf(stdout, "\n");
	system("pause");
	return 0;
}

测试结果：