#ifndef __OJ_H__#define __OJ_H__#include <vector>#include<string.h> #include <iostream>#include <stack>using namespace std;enum{    EAST = 1,    SOUTH = 2,    WEST = 3,    NORTH = 4,    BLOCK = 4,};// 节点坐标类型typedef struct{    // 坐标    int x;    int y;}structLoc;// 节点类型typedef struct{    // 是否已经标记过,true表示已标记    bool bMark;    char chPoint;}structPoint;// 栈元素类型typedef struct{    // 搜索深度     int depth;    // 坐标    int x;    int y;    // 搜索方向    int dir;}StackType;int SSavep(char *visited, int t, int n, int m);// 当前节点是否可通bool IsBlock(structLoc curLoc, vector<vector<structPoint>> vecMaze);// 节点标记为已走过void setFootStep(structLoc curLoc, vector<vector<structPoint>>& vecMaze);// 到达终点bool IsEnd(structLoc curLoc);// 下一个节点void GetNextPoint(int x, int y, structLoc& curLoc, int dir);// 深度优先搜素int DepthFirstSearch(structLoc& curLoc, int dir, int idepth, int iTime, StackType sElement, vector<vector<structPoint>>& vecMaze);#endif

#include<stdio.h> #include<string.h> #include "OJ.h" // 起点和终点structLoc PointS, PointP;/*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        不可以救出公主*/ int SSavep(char *visited, int t, int n, int m){     // 构造迷宫vector;找出S和P的位置    vector<vector<structPoint> > vecMaze;    for (int i = 0; i < m; i++)    {        vector<structPoint> vecTemp;        for (int j = 0; j < n; j++)        {            if (‘S‘ == visited[(i * n) + j])            {                PointS.x = j;                PointS.y = i;            }            if (‘P‘ == visited[(i * n) + j])            {                PointP.x = j;                PointP.y = i;            }            structPoint sPoint;            sPoint.chPoint = visited[(i * n) + j];            sPoint.bMark = false;            vecTemp.push_back(sPoint);        }        vecMaze.push_back(vecTemp);    }    // 当前节点坐标    structLoc curLoc;    curLoc.x = PointS.x;    curLoc.y = PointS.y;    // 搜索深度    int iDepth = 0;    // 栈元素    StackType sElement;    // 节点栈    stack<StackType> stackPoint;    do    {        if (!IsBlock(curLoc, vecMaze))        {            setFootStep(curLoc, vecMaze);            sElement.depth = iDepth;            sElement.dir = EAST;            sElement.x = curLoc.x;            sElement.y = curLoc.y;            // 当前节点入栈            stackPoint.push(sElement);            if (IsEnd(curLoc))            {                return sElement.depth > t?-1:0;            }            else            {                // 下一个节点                GetNextPoint(sElement.x, sElement.y, curLoc, EAST);                iDepth++;            }        }        else        {            if (!stackPoint.empty())            {                // 回退到上一层深度继续搜索                sElement = stackPoint.top();                stackPoint.pop();                // 节点四个方向都不通,弹出栈                while ((BLOCK == sElement.dir) && (!stackPoint.empty()))                {                    sElement = stackPoint.top();                    stackPoint.pop();                }                // 如果还有其他方向没搜索过，换一个方向搜索                if (BLOCK != sElement.dir)                {                    sElement.dir++;                    stackPoint.push(sElement);                    GetNextPoint(sElement.x, sElement.y, curLoc, sElement.dir);                }            }        }    }    while(!stackPoint.empty());        // 没有找到通路    return -1;}  bool IsBlock(structLoc curLoc, vector<vector<structPoint>> vecMaze){    // 遇到边界    if ((curLoc.x < 0)        || (curLoc.x >= (int)vecMaze.front().size())        || (curLoc.y < 0)        || (curLoc.y >= (int)vecMaze.size()))    {        return true;    }    // 遇到墙    structPoint sPoint = vecMaze.at(curLoc.y).at(curLoc.x);    if (sPoint.chPoint == ‘*‘)    {        return true;    }    // 已经标记过    if (true == sPoint.bMark)    {        return true;    }    return false;}void setFootStep(structLoc curLoc, vector<vector<structPoint>>& vecMaze){    vecMaze.at(curLoc.y).at(curLoc.x).bMark = true;}bool IsEnd(structLoc curLoc){    if ((curLoc.x == PointP.x) && (curLoc.y == PointP.y))    {        return true;    }    return false;}void GetNextPoint(int x, int y, structLoc& curLoc, int dir){    if (EAST == dir)    {        curLoc.x = x + 1;        curLoc.y = y;    }    else if (SOUTH == dir)    {        curLoc.x = x;        curLoc.y = y + 1;    }    else if (WEST == dir)    {        curLoc.x = x - 1;        curLoc.y = y;    }    else if (NORTH == dir)    {        curLoc.x = x;        curLoc.y = y - 1;    }    else    {    }}