题解
- 迷宫问题既可以用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）
这个代码，
#include <iostream>
#include <stack>
using namespace std;
class Box
{
int x;
int y;
int di;//di代表下一步的方向，0向右，1向下，2向左，3向上
public:
Box();
friend class Maze;
};
class Maze
{
private:
int n, m;
int **maze;
int directx[4], directy[4];//分别对应在不同di下，走到下一格x和y需要变化的值。
public:
int num;//记录深度，即总路程
Maze(int n1, int m1);
~Maze();
int FindPath();
};
Maze::Maze(int n1, int m1)
{
n = n1+2;//将迷宫用一层值为1的墙包起来
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;
else
maze[i][j] = 1;
}
else
maze[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;//将出栈的temp的各成员存起来，之后temp就能重新用
int y = temp.y;
int di = temp.di+1;
while(di<4)
{
int line = x+directx[di];//定义新变量对x和y操作就不会改变其值，方便循环操作。
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;
else
di = 0;
}
else
di++;
}
}
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;
else
cout<<"God please help our poor hero."<<endl;
}
return 0;
}
代码块（BFS）
#include <iostream>
#include <queue>
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;
else
maze[i][j] = 1;
}
else
maze[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)
{//一旦有某一条到达了终点，则说明其是所有通路中最短的，将其step输出即可
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;
}