DFS 고전 템 플 릿 문제 --- 미로 (경로 출력)

제목 설명: 하나의 미로 문제 에 대한 구 해 요 구 를 실현 합 니 다. nxn 의 행렬 을 입력 하고 0 으로 도 로 를 대표 하 며 1 로 장애물 을 대표 하 며 알고리즘 을 실현 합 니 다. 입구 (기본 값 은 왼쪽 상단) 에서 출구 (기본 값 은 오른쪽 하단) 까지 의 노선 을 제시 해 야 합 니 다.첫 줄 n 을 입력 하 십시오.두 번 째 줄 은 왼쪽 상단 (1, 1) 에서 오른쪽 하단 (n, n) 까지 출력 하 는 행렬 (사방 경계선 1) 입 니 다.테스트 용례 확보 통로

//#include 
#include
#include
#include
#include
using namespace std;
int n;
int map[105][105];//   
int vis[105][105];//        
int next_Step[4][2]={{1,0},{0,-1},{-1,0},{0,1}};//       ，     
int cnt;//        
int step;//     
struct point{//            
	int x,y;
}p;
stack<point> path,temp;//      ，     ，       （      ） 
 
void dfs(int sx,int sy,int step){
	if(sx==n && sy==n){//          
	    printf("**path%d**
",++cnt); 
		while(!path.empty()){//     
			point p1=path.top();//      
			path.pop();//   
			temp.push(p1);//p1  temp 
		}
		while(!temp.empty()){//  temp    
			point p1=temp.top();
			temp.pop();
			path.push(p1);
			printf("-->(%d,%d)",p1.x,p1.y);
		}
		printf("
");
		printf("steps of the path%d:%d",cnt,step);
		printf("
");
		return ;
	}
	if(sx<1 || sx>n || sy<1 || sy>n){//     return  
		return;
	}
	for(int i=0;i<4;i++){//        
		int ex=sx+next_Step[i][0];//     
		int ey=sy+next_Step[i][1];
		if(ex>=1 && ex<=n && ey>=1 && ey<=n && map[ex][ey]==0 && vis[ex][ey]==0){//  （    ） 
			vis[ex][ey]=1;//      
			p.x=ex;
			p.y=ey;
			path.push(p);//      
			dfs(ex,ey,step+1);//         
			vis[ex][ey]=0; //    
			path.pop();//    ，          
		}
	}
	return ;
}
int main(){
	cnt = 0;
	p.x = 1;
	p.y = 1;
	path.push(p);
	cin >> n;
	for(int i=0;i<=n+1;i++)
	{
		for(int j=0;j<=n+1;j++)
		{
			if(i==0||j==0||i==n+1||j==n+1){
				map[i][j]=1;
			}else{
				vis[i][j] = 0;
			    scanf("%d",&map[i][j]);
			}
		}
	}
	for(int i=0;i<=n+1;i++)
	{
		for(int j=0;j<=n+1;j++)
		{
			printf("%d ",map[i][j]);
		}
		printf("
");
	}
	dfs(1,1,0);
	
	return 0;
}

Tips: 만약 에 출력 미로 만 몇 개의 경로 가 있다 면 제목 은 매우 간단 할 것 입 니 다. 여 기 는 모든 가능 한 경 로 를 제공 해 야 하기 때문에 디자인 할 때 두 개의 스 택 을 만들어 야 합 니 다. 한 경로 스 택 에 임시 스 택 을 만들어 야 합 니 다. 이 곳 은 주의 와 기술 이 필요 합 니 다.전체적으로 말 하면 이 문 제 는 dfs 의 템 플 릿 문제 로 손 을 많이 연습 할 수 있 습 니 다 ~