题解 | #迷宫问题#

#include<iostream>
#include<vector>
#include<set>
#include<cstdio>
#include<string>
#include <unordered_map>
#include<map>
using namespace std;
map<int,pair<int, int>> indexMap;//map容器是有序的容器，会按照键的大小进行排序；unordered_map是无序的，对其排序需要写另外的代码。
                                //用来记录当前走的步数和该步数对应的坐标
int n,m;
string str1;
char str[100];


int a[100][100]; //记录当前位置是否为障碍物 1 表示为障碍物 0 表示平地
int b[100][100]={0};//记录当前位置是否走过  1表示走过 0 表示未走过
//int c[100][100]={0};
void dfs(int x,int y,int num){
	if(x==n-1 && y==m-1){
		b[x][y]=1;
		num=num+1;
        indexMap[num]=pair(x,y);
		//c[x][y]=num;

        for (const auto& pair : indexMap) {
        std::cout  << "(" << pair.second.first << "," << pair.second.second << ")" << std::endl;
    }



		//cout<<num<<"jieshu ";
		/*
        for (int j =1;j<=num;j++){
		    for (int i = 0;i<n;i++){
			    for(int k = 0;k<m;k++){
				    if(c[i][k]==j){
					    sprintf(str,"(%d,%d)",i,k);
					    std::string str1(str);
					    std::cout << str1 << std::endl;
				    }
				
			    }
			
		    }
	    }
		*/
		/*for (int i = 0;i<n;i++){
			for(int j = 0;j<m;j++){
				
				if(b[i][j]==1){
					cout<<'('<<i<<','<<j<<')'<<endl;	
				}
				
				//cout<<b[i][j]<<' ';
			
			}
			//cout<<endl;
		}
		*/
		return ;
	}
	//ËÑË÷˳ÐòΪ  ÓÒÏÂ×óÉÏ
	//左走判断
	if(y+1<m && a[x][y+1]==0 && b[x][y+1]==0){
		b[x][y]=1;
		num=num+1;
		//c[x][y]=num;
        indexMap[num]=pair(x,y);
		//cout<<num<<"you";
		dfs(x,y+1,num);
		b[x][y]=0;          //回退时要恢复当前位置的状态和清除该步数对应的坐标。
        indexMap.erase(num);
		num=num-1;
	}
	//下走判断
	if(x+1<n && a[x+1][y]==0 && b[x+1][y]==0){
		b[x][y]=1;
		num=num+1;
        indexMap[num]=pair(x,y);
		//c[x][y]=num;
		//cout<<num<<"xia";
		dfs(x+1,y,num);
		b[x][y]=0;
        indexMap.erase(num);
		num=num-1;
	}
	//右走判断
	if(y-1>=0 && a[x][y-1]==0 && b[x][y-1]==0){
		b[x][y]=1;
		num=num+1;
		//c[x][y]=num;
        indexMap[num]=pair(x,y);
		//cout<<num<<"zuo";
		dfs(x,y-1,num);
		b[x][y]=0;
        indexMap.erase(num);
		num=num-1;
	} 
	//上走判断
	if(x-1>=0 && a[x-1][y]==0 && b[x-1][y]==0){
		b[x][y]=1;
		num=num+1;
		//c[x][y]=num;
        indexMap[num]=pair(x,y);
		//cout<<num<<"shang";
		dfs(x-1,y,num);
		b[x][y]=0;      
        indexMap.erase(num);
		num=num-1;
	}
	
	
	return ;
}



int main(){
	cin>>n>>m;
	for (int i = 0;i<n;i++){
		for(int j = 0;j<m;j++){
			cin>>a[i][j];
		}
	}
	int num= 0;
	dfs(0,0,num);
	//ËÑË÷˳ÐòΪ  ÓÒÏÂ×óÉÏ 
/*
	for (int i = 0;i<n;i++){
		for(int j = 0;j<m;j++){
			cout<<c[i][j]<<' ';
		}
		cout<<endl;
	}
	cout<<num<<endl;
    */
	/*for (int j =1;j<=num;j++){
		for (int i = 0;i<n;i++){
			for(int k = 0;k<m;k++){
				if(c[i][k]==j){
					sprintf(str,"(%d,%d)",i,k);
					std::string str1(str);
					std::cout << str1 << std::endl;
				}
				
			}
			
		}
	}*/
	
		
	return 0;
}