스 택 의 응용 - 깊이 우선 검색 (2) 정확 한 경 로 를 출력 합 니 다.
2011 단어 데이터 구조 - 스 택 과 대기 열
지난 미로 로 가 는 블 로그 에는 미로 에서 어떻게 벗 어 나 는 지, 이번 에는 그 승화 일 뿐, 어떻게 정확 한 노선 을 출력 할 수 있 을 까?
컴퓨터 는 여러 경 로 를 끝까지 시도 해 봐 야 마지막 종점 을 찾 을 수 있 기 때문에 정확 한 노선 을 어떻게 출력 하 는 지도 쉽 지 않다.
구체 적 인 코드 는 다음 과 같다.
my stack. h 와 my stack. cpp 는 미로 로 가 는 것 과 같 습 니 다. 뒤 져 볼 수 있 습 니 다. 깊이 우선 검색 。
main 함수 코드 는 다음 과 같 습 니 다.
#include
#include"mystack.h"
#include
#define MAXROW 10
#define MAXLINE 10
// 10
using namespace std;
Stack s; // ,
Point prePoint[MAXROW][MAXLINE];//
int maze[MAXROW][MAXLINE] =
{
1,1,1,1,1,1,1,1,1,1,
0,0,0,1,1,1,1,1,1,1,
1,1,0,1,1,1,1,1,1,1,
1,1,0,0,0,0,1,1,1,1,
1,1,0,1,1,0,1,1,1,1,
1,1,0,1,0,0,0,1,1,1,
1,1,1,1,1,0,1,1,1,1,
1,1,1,1,1,0,0,0,1,1,
1,1,1,1,1,1,1,0,0,0,
1,1,1,1,1,1,1,1,1,1,
};
void displyMaze()
{
for(int i=0; i< MAXROW; i++)
{
for(int j=0; j=0&&maze[t._x-1][t._y] == 0)
visit(t._x-1,t._y,t); // t ,
//
if(t._x+1<=9&&maze[t._x+1][t._y] == 0)
visit(t._x+1,t._y,t);
//
if(t._y-1>=0&&maze[t._x][t._y-1] == 0)
visit(t._x,t._y-1,t);
//
if(t._y+1<=9&&maze[t._x][t._y+1] == 0)
visit(t._x,t._y+1,t);
if(t._x==ep._x&&t._y==ep._y)
{
flag=0; //
destroyStack(&s);
break;
}
}
#endif
if(flag==0)
{
cout<