题解 | #迷宫问题#

//主题：深搜迷宫问题 求最短路径的详细走法 
//思路：深搜 将路径存储在数组中 求得最短路径长度时 现在的这个数组存储的路径就是最短路径的走法 
#include<bits/stdc++.h>
using namespace std;
//迷宫规模，迷宫，计算过程中存储路径的数组,存储最终结果的数组，最短路径长度
int n,m,a[11][11],book[11][11],ans[11][11],min_step=999;
void dfs(int row,int col,int step)//参数为当前所在行数，当前所在列数，当前走的步数
{
	if(row==n-1 && col==m-1){//到达右下角 
		if(step<min_step){
			min_step=step; 
		}
		//将当前最优可行解存储下来
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				ans[i][j]=book[i][j];
			}
		}
		return;//如果到达了右下角就不用往下搜索了 
	}
	
	//没有到达右下角，继续往下一个点搜索
	int next[4][2]={
		{0,1},//向右走，行数不变，列数增加1 
		{1,0},// 向下走，行数增加1，列数不变 
		{0,-1},// 向左走，行数不变，列数减小1 
		{-1,0},// 向上走，行数减小1，列数不变 
	};
	int nr,nc;//next_row,next_column;下一个点的行数和列数 
	for(int i=0;i<=3;i++){
		nr=row+next[i][0];
		nc=col+next[i][1];
		if(nr<0 || nr>n-1 || nc<0 || nc>m-1){//越界 
			continue; 
		}
		if(a[nr][nc]==0 && book[nr][nc]==0){//该点是空地并且没有被走过 
			book[nr][nc]=1;//标记已走过，自断来路，以免回头 
			dfs(nr,nc,step+1);//开始尝试下一个点 
			book[nr][nc]=0;//将这个点置为0 
		}
	} 
	
	return; 
 } 
 void output(int row,int col){//深度优先方式输出ans数组中存储的路径 
 	if(row==n-1 && col==m-1){//到达右下角 
 		printf("(%d,%d)\n",row,col); //打印这一步的行列数,实际上就是右下角位置 
		ans[row][col]=0; //自断来路，避免回头
		return;
	}
	//没有到达右下角，继续往下一个点搜索
	int next[4][2]={
		{0,1},//向右走，行数不变，列数增加1 
		{1,0},// 向下走，行数增加1，列数不变 
		{0,-1},// 向左走，行数不变，列数减小1 
		{-1,0},// 向上走，行数减小1，列数不变 
	};
	int nr,nc;//next_row,next_column;下一个点的行数和列数 
	for(int i=0;i<=3;i++){
		nr=row+next[i][0];
		nc=col+next[i][1];
		if(nr<0 || nr>n-1 || nc<0 || nc>m-1){//越界 
			continue; 
		}
		if(ans[nr][nc]==1){//找到下一步的点 
			printf("(%d,%d)\n",row,col); //打印这一步的行列数
			ans[row][col]=0;//自断来路，避免回头 
			output(nr,nc); //以下一个点作为起点继续向下搜索 
			return;//注意这一个return很重要，在上一行，更深一层的递归结束之后
				   //这一层递归也应该结束了。 因为只要递归开始返回，就说明
				   //已经触达了终点，路径也已经打印出来了，所以不用再做任何操作，
				   //只需要结束这些递归函数的运行即可。	
		}
	} 
 }
int main(){
	cin>>n>>m;
	//book全部赋值为0	
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			book[i][j]=0;
		}
	} 	
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cin>>a[i][j];
		}
	} 
	book[0][0]=1;//起点标注为1表示走过的
	dfs(0,0,0); //从0行0列出发，到达n-1行，m-1列,初始步数为0 
	output(0,0); //从左上角出发，深度优先方式将ans中路径打印出来 
	return 0;
}