用堆栈实现迷宫问题，二维数组表示迷宫：1表示墙壁，0表示可以走的路，只能横着走或竖着走
成都创新互联公司是专业的大关网站建设公司，大关接单;提供
成都做网站、成都网站设计,网页设计,网站设计,建网站,PHP网站建设等专业做网站服务;采用PHP框架,可快速的进行大关网站开发网页制作和功能扩展;专业做搜索引擎喜爱的网站,专业的做网站团队,希望更多企业前来合作!
不能斜着走，要求编程实现找到从左上角到右下角的路线
//深度优先：有解就退出搜索（不一定是最优解）
#include
#include
using namespace std;
#define ROW 5
#define COL 5
typedef struct point
{
int _row;
int _col;
}Point;
Point stack[512];
int top= 0;
void Push(Point& p)
{
stack[top++] = p;
}
const Point& Pop()
{
return stack[--top];
}
int IsEmpty()
{
return top==0;
}
int maze[ROW][COL] = {
{ 0, 0, 0, 0, 0 },
{ 0, 1, 1, 1, 0 },
{ 0, 1, 1, 0, 0 },
{ 0, 1, 1, 0, 1 },
{ 0, 0, 0, 0, 0 },
};
void PrintMaze()
{
for (int i = 0; i < ROW; ++i)
{
for (int j = 0; j < COL; ++j)
{
cout << maze[i][j] << " ";
}
cout << endl;
}
cout << endl;
}
Point Prev[ROW][COL] = {
{ { -1, -1 }, { -1, -1 }, { -1, -1 }, { -1, -1 }, { -1, -1 } },
{ { -1, -1 }, { -1, -1 }, { -1, -1 }, { -1, -1 }, { -1, -1 } },
{ { -1, -1 }, { -1, -1 }, { -1, -1 }, { -1, -1 }, { -1, -1 } },
{ { -1, -1 }, { -1, -1 }, { -1, -1 }, { -1, -1 }, { -1, -1 } },
{ { -1, -1 }, { -1, -1 }, { -1, -1 }, { -1, -1 }, { -1, -1 } },
};
void Visit(int row, int col,Point& p)
{
Point tmp = { row, col};
maze[row][col] = 2;
Prev[row][col] = p;
Push(tmp);
}
void Test1()
{
Point p = { 0, 0};
maze[p._row][p._col] = 2;
Push(p);
while (!IsEmpty())
{
p = Pop();
if (p._row == ROW - 1 && p._col == COL - 1)
break;
//up
if (p._row - 1 >= 0 && maze[p._row - 1][p._col] == 0)
Visit(p._row - 1, p._col,p);
//down
if (p._row + 1 < ROW&&maze[p._row + 1][p._col] == 0)
Visit(p._row + 1, p._col,p);
//left
if (p._col - 1 >= 0 && maze[p._row][p._col - 1] == 0)
Visit(p._row, p._col - 1,p);
//right
if (p._col + 1 < COL&&maze[p._row][p._col + 1] == 0)
Visit(p._row, p._col + 1,p);
}
if (p._row == ROW - 1 && p._col == COL - 1)
{
printf("(%d,%d)\n", p._row, p._col);
while ((Prev[p._row][p._col])._row != -1)
{
p = Prev[p._row][p._col];
printf("(%d,%d)\n", p._row, p._col);
}
}
else
cout << "no path!\n";
}
//广度求得最优路径，找到后停止搜索
#include
using namespace std;
#define ROW 5
#define COL 5
typedef struct point
{
int _row;
int _col;
int _prev;
}Point;
Point queue[512];
int head = 0;
int tail = 0;
void Enqueue(Point& p)
{
queue[tail++] = p;
}
const Point& Dequeue()
{
return queue[head++];
}
int IsEmpty()
{
return head == tail;
}
int maze[ROW][COL] = {
{ 0, 0, 0, 0, 0 },
{ 0, 1, 1, 1, 0 },
{ 0, 1, 1, 0, 0 },
{ 0, 1, 1, 0, 1 },
{ 0, 0, 0, 0, 0 },
};
void PrintMaze()
{
for (int i = 0; i < ROW; ++i)
{
for (int j = 0; j < COL; ++j)
{
cout << maze[i][j] << " ";
}
cout << endl;
}
cout << endl;
}
void Visit(int row, int col)
{
Point tmp = { row, col, head - 1 };
maze[row][col] = 2;
Enqueue(tmp);
}
void Test1()
{
Point p = { 0, 0, -1 };
maze[p._row][p._col] = 2;
Enqueue(p);
while (!IsEmpty())
{
p = Dequeue();
if (p._row == ROW - 1 && p._col == COL - 1)
break;
//up
if (p._row - 1 >= 0 && maze[p._row - 1][p._col] == 0)
Visit(p._row - 1, p._col);
//down
if (p._row + 1 < ROW&&maze[p._row + 1][p._col] == 0)
Visit(p._row + 1, p._col);
//left
if (p._col - 1 >= 0 && maze[p._row][p._col - 1] == 0)
Visit(p._row, p._col - 1);
//right
if (p._col + 1 < COL&&maze[p._row][p._col + 1] == 0)
Visit(p._row, p._col + 1);
}
if (p._row == ROW - 1 && p._col == COL - 1)
{
printf("(%d,%d)\n", p._row, p._col);
while (p._prev != -1)
{
p = queue[p._prev];
printf("(%d,%d)\n", p._row, p._col);
}
}
else
cout << "no path!\n";
}
创新互联www.cdcxhl.cn，专业提供香港、美国云服务器，动态BGP最优骨干路由自动选择，持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证， 机房独有T级流量清洗系统配攻击溯源，准确进行流量调度，确保服务器高可用性。佳节活动现已开启，新人活动云服务器买多久送多久。
本文名称：迷宫问题的求解方式：应用深度优先和广度优先的搜索-创新互联
当前地址：
http://cdkjz.cn/article/hpigj.html
