# 回溯法解决迷宫问题

0表示墙壁，1表示通路，函数参数传入迷宫起点，每次向前一步则把前一步设置为2，防止再次试探该位置。

``````void SearchMazePath(Pos entry) //求取通路 回溯法（迭代）
{
Stack *s;
Pos next = entry;
PushStack(&s,next);
do
{
Maze[next._x][next._y] = 2;
next = TopStack(s);
next._x += 1; //下
if (CheckCoord(next))
{
PushStack(&s,next);
continue;
}

next = TopStack(s);
next._x -= 1;//上
if (CheckCoord(next))
{
PushStack(&s,next);
continue;
}

next = TopStack(s);
next._y += 1;//右
if (CheckCoord(next))
{
PushStack(&s,next);
continue;
}

next = TopStack(s);
next._y -= 1;//左
if (CheckCoord(next))
{
PushStack(&s,next);
continue;
}

PopStack(&s);  //改层没有通路，则pop掉栈顶，返回到上一层继续试探其他方向
next = TopStack(s);
}while (EmptyStack(s) && next._x != entry._x);
}``````

``````void SearchMazePathR(Pos entry) //求取通路（递归）
{
Pos next = entry;
Maze[next._x][next._y] = 2;

next = entry;
next._x -=1;
if (CheckCoord(next))
SearchMazePathR(next);

next = entry;
next._x +=1;
if (CheckCoord(next))
SearchMazePathR(next);

next = entry;
next._y -=1;
if (CheckCoord(next))
SearchMazePathR(next);

next = entry;
next._y +=1;
if (CheckCoord(next))
SearchMazePathR(next);
}``````

``````int CheckCoord(Pos pos)
{
if (pos._x >= 0 && pos._xpos._y >=0 && pos._ypos._x][pos._y] == 1)
{
return 1;
}
else
return 0;
}``````

``````void SearchShortPathR(Pos entry,Pos cur) //寻找最短路径
{
Pos next = entry;
Pos prev = cur;
Maze[next._x][next._y] = Maze[prev._x][prev._y] + 1;
if (next._y == COL-1)
printf("Exit:(%d ,%d)\n",next._x,next._y);  //打印出口

next = entry;
next._x += 1;
if (CheckCoordS(next,entry))
SearchShortPathR(next,entry);

next = entry;
next._x -= 1;
if (CheckCoordS(next,entry))
SearchShortPathR(next,entry);

next = entry;
next._y += 1;
if (CheckCoordS(next,entry))
SearchShortPathR(next,entry);

next = entry;
next._y -= 1;
if (CheckCoordS(next,entry))
SearchShortPathR(next,entry);
}``````

1.针对所给问题，定义问题的解空间；
2.确定易于搜索的解空间结构；
3.以深度优先方式搜索解空间，并在搜索过程中用必要的条件避免无效搜索。