OJ-营救公主

题目：
公主被魔王抓走了，王子需要拯救出美丽的公主。他进入了魔王的城堡，魔王的城堡是一座很大的迷宫。为了使问题简单化，我们假设这个迷宫是一个N*M的二维方格。迷宫里有一些墙，王子不能通过。王子只能移动到相邻（上下左右四个方向)的方格内，并且一秒只能移动一步，就是说，如果王子在(x,y）一步只能移动到(x-1,y),(x+1,y),(x,y-1),(x,y+1)其中的一个位置上。地图由‘S’，‘P’，‘.’，‘*’四种符号构成，‘.’表示王子可以通过，‘*’表示墙，王子不能通过；'S'表示王子的位置；‘P’表示公主的位置；T表示公主存活的剩余时间，王子必须在T秒内到达公主的位置，才能救活公主。
例如：
S。。
×。×
。P×
至少需要3秒才能营救到公主，否则时间不够。

代码（拷贝别人，略修改）

#include <stdio.h>
#include <string.h>
#include <malloc.h>
#include "OJ.h"

/*
Description
     每组测试数据以三个整数N,M,T(0<n, m≤20, t>0)开头，分别代表迷宫的长和高，以及公主能坚持的天数。
     紧接着有M行，N列字符，由"."，"*"，"P"，"S"组成。其中 "." 代表能够行走的空地。 "*" 代表墙壁，Jesse不能从此通过。
     "P" 是公主所在的位置。 "S" 是Jesse的起始位置。 每个时间段里Jesse只能选择“上、下、左、右”任意一方向走一步。
Prototype
     int SSaveP (int *maze[], int M, int n, int t)
Input Param
     maze            迷宫布局（这里用二维数组实现布局）
     M               迷宫（数组）行数
     N               迷宫（数组）列数
     T               公主能坚持的天数
Output Param
                     无
Return Value
     0         可以救出公主
     -1        不可以救出公主

*/
 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
 */
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");
            int rt = cur_step->level;
            queue_release(queue);
            return rt;
        }
        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 SSavep(char *maze_data, int time, int N, int M)
{
    // 这里面添加函数功能
    struct room_info* maze = NULL;
    struct room_info* prince = NULL;
    int time_need = 0;

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

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

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

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

注：广度优先搜索，用队列存储遍历。