【C++题解】1431. 迷宫的第一条出路

问题：1431. 迷宫的第一条出路

类型：深度搜索、回溯、路径打印

题目描述：

已知一 N×N 的迷宫，允许往上、下、左、右四个方向行走，现请你按照左、上、右、下顺序进行搜索，找出第一条从左上角到右下角的路径。

输入：

输入数据有若干行，第一行有一个自然数 N（N≤20），表示迷宫的大小；
其后有 N 行数据，每行有 N 个 0 或 1（数字之间没有空格，0 表示可以通过，1 表示不能通过），用以描述迷宫地图。入口在左上角 (1,1)处，出口在右下角(N,N) 处。
所有迷宫保证存在从入口到出口的可行路径。

输出：

输出数据仅一行，为按照要求的搜索顺序找到的从入口到出口的第一条路径（搜索顺序：左、上、右、下）。

样例：

输入：

4
0001
0100
0010
0110

输出：

(1,1)->(1,2)->(1,3)->(2,3)->(2,4)->(3,4)->(4,4)

完整代码如下：

#include<bits/stdc++.h> 
using namespace std;
int n,mg[30][30],bj[1000][1000]; 

int  dfs(int x,int y,int k){
	if(x<1||x>n||y<1||y>n||mg[x][y]!=0){
		return k;
	}
	
	bj[k][1]=x;
	bj[k][2]=y;
	mg[x][y]=1;
	
	if(x==n&&y==n){
		//五、输出结果 
		for(int i=1;i<=k;i++){
			cout<<"("<<bj[i][1]<<","<<bj[i][2]<<")";
			if(i!=k){
				cout<<"->";
			}
		}
	}
	//左 
	dfs(x,y-1,k+1); 
	//上
	dfs(x-1,y,k+1);
	//右
	dfs(x,y+1,k+1);
	//下 
	dfs(x+1,y,k+1);
	
	
	
	
}

int main(){
	//一、分析问题
	//已知：N×N 的迷宫，允许往上、下、左、右四个方向行走。 
	//未知：按照左、上、右、下顺序进行搜索，找出第一条从左上角到右下角的路径。
	//关系：深度搜索、回溯

	
	//二、数据定义 

	//三、数据输入
	cin>>n; 
	for(int i=1;i<=n;i++){
		string s;
		cin>>s;
		for(int j=1;j<=n;j++){
			mg[i][j]=s[j-1]-'0';
		}
	}
	//四、数据计算 
	dfs(1,1,1);


	return 0;	
}