Question

高分求用c或c++做迷宫的代码，要求分别用深度和广度优先算法

Answer 1

先给个版本，你先看看：

/*
//运行的一个例子,1表示有障碍，0表示可以通过
Enter maze size
5
Enter maze in row major order
1 1 0 0 1
0 0 1 0 1
0 1 1 0 1
0 0 0 0 0
0 0 0 0 0
The path is
4 5
4 4
4 3
4 2
4 1
3 1
2 1
1 1
Press any key to continue
*/

#include <iostream.h>

class Position {
friend bool InputMaze();
friend void OutputPath();
friend bool FindPath();
public:
operator int() const {return row;}
private:
int row, col;
};

template <class T>
void Make2DArray(T ** &x, int rows, int cols)
{
x = new T * [rows];
for (int i = 0; i < rows; i++)
x[i] = new T [cols];
}

template<class T>
class Stack {
// LIFO objects
public:
Stack(int MaxStackSize = 10);
~Stack() {delete [] stack;}
bool IsEmpty() const {return top == -1;}
bool IsFull() const {return top == MaxTop;}
T Top() const;
Stack<T>& Add(const T& x);
Stack<T>& Delete(T& x);
private:
int top; // current top of stack
int MaxTop; // max value for top
T *stack; // element array
};

template<class T>
Stack<T>::Stack(int MaxStackSize)
{// Stack constructor.
MaxTop = MaxStackSize - 1;
stack = new T[MaxStackSize];
top = -1;
}

template<class T>
T Stack<T>::Top() const
{
return stack[top];
}

template<class T>
Stack<T>& Stack<T>::Add(const T& x)
{
stack[++top] = x;
return *this;
}

template<class T>
Stack<T>& Stack<T>::Delete(T& x)
{
x = stack[top--];
return *this;
}

// globals
int **maze, m;
Stack<Position> *path; // pointer to stack

void welcome() {};

bool InputMaze()
{// Input the maze.
cout << "Enter maze size" << endl;
cin >> m;
Make2DArray(maze, m+2, m+2);
cout << "Enter maze in row major order" << endl;
for (int i=1; i<=m; i++)
for (int j=1; j<=m; j++) cin >> maze[i][j];
return true;
}

bool FindPath()
{// Find a path from (1,1) to the exit (m,m).
// Return true if successful, false if impossible.
// Throw NoMem exception if inadequate space.

path = new Stack<Position>(m * m - 1);

// initialize offsets
Position offset[4];
offset[0].row = 0; offset[0].col = 1; // right
offset[1].row = 1; offset[1].col = 0; // down
offset[2].row = 0; offset[2].col = -1; // left
offset[3].row = -1; offset[3].col = 0; // up

// initialize wall of obstacles around maze
for (int i = 0; i <= m+1; i++) {
maze[0][i] = maze[m+1][i] = 1; // bottom and top
maze[i][0] = maze[i][m+1] = 1; // left and right
}

Position here;
here.row = 1;
here.col = 1;
maze[1][1] = 1; // prevent return to entrance
int option = 0; // next move
int LastOption = 3;

// search for a path
while (here.row != m || here.col != m) {// not exit
// find a neighbor to move to
int r, c;
while (option <= LastOption) {
r = here.row + offset[option].row;
c = here.col + offset[option].col;
if (maze[r][c] == 0) break;
option++; // next option
}

// was a neighbor found?
if (option <= LastOption) {// move to maze[r][c]
path->Add(here);
here.row = r; here.col = c;
// set to 1 to prevent revisit
maze[r][c] = 1;
option = 0;
}
else {// no neighbor to move to, back up
if (path->IsEmpty()) return false;
Position next;
path->Delete(next);
if (next.row == here.row)
option = 2 + next.col - here.col;
else option = 3 + next.row - here.row;
here = next;
}
}

return true; // at exit
}

void OutputPath()
{// Output path to exit.
cout << "The path is" << endl;
Position here;
while (!path->IsEmpty()) {
path->Delete(here);
cout << here.row << ' ' << here.col << endl;}
}

void main(void)
{
welcome();
InputMaze();
if (FindPath()) OutputPath();
else cout << "No path" << endl;
}

追问

我已经自己做出来了

追答

哥们厉害，不用到这儿来的。

追问

我是女的，谢谢=_=

还有你给的太简单不是我要的

追答

没注意，楼主是妹子。那就更厉害了！

Answer 2

问题能具体点吗？比如输入输出是要求怎样的？

追问

我自己写了一个有错

Answer 3

踩一脚，待会下课了回去写给你！

追问

真的假的

这么好

什么时候下课啊

追答

额，看样子都已经做出来了，那下次再帮你解决问题。