题解
- 迷宫问题既可以用DFS也可以用BFS。DFS的优点在于方便得到起点到终点的准确路径，而BFS优点则是较为简单，且得到的路径长度是起点到终点的最短路径。
...xxxx
.x.x...
.x.x.x.
.x...x.
.xxxxx.
.......
比如这个迷宫用DFS得到的就不是最短路径，而BFS在每增加一步时会包含该步所有可能的通路，所以最先到终点的就一定最短路径。
题目
问题 E: 拯救公主 (Ver. I)时间限制: 1 Sec 内存限制: 128 MB
提交: 112 解决: 30
[提交][状态][讨论版]
题目描述公主被BEelzebub feng5166绑架，我们的英雄Ignatius必须拯救我们漂亮的公主。现在他进入了feng5166的城堡。城堡是一个大型的迷宫。为了简单地解决这个问题，我们假设迷宫是一个N * M的二维数组，左上角是（0,0），右下角是（N-1，M-1）。Ignatius进入（0,0），feng5166房间的门是（N-1，M-1），这是我们的目标。这是一些规则：1.Ignatius只能向四个方向（上，下，左，右）移动，一步一秒。步骤定义如下：如果当前位置为（x，y），则在步骤之后，Ignatius只能站在（x-1，y），（x + 1，y），（x，y-1）或（X，Y + 1）。
2.数组标有一些字符和数字，定义如下
.：Ignatius可以走路的地方。
X：这个地方是一个陷阱，Ignatius不能走在上面。你的任务是给出Ignatius达到目标位置所需的最小秒数。您可以假设起始位置和目标位置永远不会成为陷阱。输入测试数据有多组
每个测试样例以包含两个数字N和M（2 <= N <= 100,2 <= M <= 100）的行开始，这表示迷宫的大小。
然后是N * M二维矩阵，描述整个迷宫。
输入格式见样例输入输出对于每个测试样例
你应该输出“God please help our poor hero.”。 如果Ignatius无法到达目标位置，或者你应该输出“It takes n seconds to reach the target position.”（n是最小秒数）样例输入5 6
.XX...
..X...
....X.
...XX.
XXXXX.
5 6
.XX...
..X...
.XX.X.
....X.
XXXXX.
5 6
.XX...
..XX..
....X.
...XX.
XXXXX.样例输出It takes 11 seconds to reach the target position.
It takes 13 seconds to reach the target position.
God please help our poor hero.
代码块（DFS）（WA）
#include
#include
using namespace std;class Box
{int x;int y;int di;
public:Box();friend class Maze;
};class Maze
{
private:int n, m;int **maze;int directx[4], directy[4];
public:int num;Maze(int n1, int m1);~Maze();int FindPath();
};Maze::Maze(int n1, int m1)
{n = n1+2;m = m1+2;maze = new int*[n];for(int i=0; i<n; i++){maze[i] = new int[m];for(int j=0; j<m; j++){char ch;if(0<i && i<n-1 && 0<j && j<m-1){cin>>ch;if(ch=='.')maze[i][j] = 0;elsemaze[i][j] = 1;}elsemaze[i][j] = 1;}}num = 1;directx[0] = 0, directx[1] = 1, directx[2] = 0, directx[3] = -1;directy[0] = 1, directy[1] = 0, directy[2] = -1, directy[3] = 0;
}Box::Box()
{x = 1;y = 1;di = -1;
}Maze::~Maze()
{for(int i=0; i<n; i++)delete []maze[i];delete []maze;
}int Maze::FindPath()
{Box temp;stack<Box> s;s.push(temp);maze[1][1] = -1;while(!s.empty()){temp = s.top();s.pop();num--;int x = temp.x;int y = temp.y;int di = temp.di+1;while(di<4){int line = x+directx[di];int col = y+directy[di];if(!maze[line][col]){temp.x = x;temp.y = y;temp.di = di;s.push(temp);x = line;y = col;maze[x][y] = -1;num++;if(x==n-2 && y==m-2)return 1;elsedi = 0;}elsedi++;}}return 0;
}int main(void)
{int n, m;while(cin>>n>>m){Maze myMaze(n, m);if(myMaze.FindPath())cout<<"It takes "<<myMaze.num<<" seconds to reach the target position."<<endl;elsecout<<"God please help our poor hero."<<endl;}return 0;
}
代码块（BFS）（AC）
#include
#include
using namespace std;class Box
{int x;int y;int di;int step;
public:Box();friend class Maze;
};class Maze
{
private:int n, m;int **maze;int directx[4], directy[4];
public:Maze(int n1, int m1);~Maze();int FindPath();
};Box::Box()
{x = 1;y = 1;di = 0;step = 0;
}Maze::Maze(int n1, int m1)
{n = n1+2;m = m1+2;maze = new int*[n];for(int i=0; i<n; i++){maze[i] = new int[m];for(int j=0; j<m; j++){char ch;if(0<i && i<n-1 && 0<j && j<m-1){cin>>ch;if(ch=='.')maze[i][j] = 0;elsemaze[i][j] = 1;}elsemaze[i][j] = 1;}}directx[0] = 0, directx[1] = 1, directx[2] = 0, directx[3] = -1;directy[0] = 1, directy[1] = 0, directy[2] = -1, directy[3] = 0;
}Maze::~Maze()
{for(int i=0; i<n; i++)delete []maze[i];delete []maze;
}int Maze::FindPath()
{Box temp;queue<Box> q;q.push(temp);maze[1][1] = 1;while(!q.empty()){temp = q.front();q.pop();int line = temp.x;int col = temp.y;int di = temp.di;int step = temp.step;while(di<4){int x = line+directx[di];int y = col+directy[di];if(!maze[x][y]){temp.x = x;temp.y = y;temp.di = 0;temp.step = step+1;q.push(temp);maze[x][y] = 1;if(x==n-2 && y==m-2){cout<<"It takes "<<temp.step<<" seconds to reach the target position."<<endl;return 1;}}di++;}}cout<<"God please help our poor hero."<<endl;return 0;
}int main(void)
{int n, m;while(cin>>n>>m){Maze myMaze(n, m);myMaze.FindPath();}return 0;
}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！
