迷宫问题（牛客）

题目描述：

定义一个二维数组N*M（其中2<=N<=10;2<=M<=10），如5 × 5数组下所示： 
int maze[5][5] = {
        0, 1, 0, 0, 0,
        0, 1, 0, 1, 0,
        0, 0, 0, 0, 0,
        0, 1, 1, 1, 0,
        0, 0, 0, 1, 0,
};
它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。入口点为[0,0],既第一空格是可以走的路。
Input
一个N × M的二维数组，表示一个迷宫。数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道。

注意：这里的唯一解指的是最短路径只有一条，但是有多种可以走出迷宫的路径

输入：输入两个整数，分别表示二位数组的行数，列数。再输入相应的数组，其中的1表示墙壁，0表示可以走的路。数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道。

5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0

输出：左上角到右下角的最短路径，格式如样例所示。

(0,0)
(1,0)
(2,0)
(2,1)
(2,2)
(2,3)
(2,4)
(3,4)
(4,4)

做题思路：

首先，必然是递归的思想，去试探出一条可以走通的路径。但必须考虑两个问题：回溯和最短路径

递归思路：

• 对于点(x,y)，首先判断是否达到终点，即x==N,y==M是否成立，如果第一次成立，就把走通的路径赋值给最短路径，之后再次走通的路径，将其长度与最短路径进行比较，如果更小，就取而代之
• 假设(x,y)就在当前可以走通的路径(即current_step)内，把(x,y)加入路径节点中，同时把(x,y)置为1表示这个节点已经走过了
• 对(x,y)的上下左右方向进行试探若是某个方向的节点可以走通，这个新节点就重复(x,y)的做法，即再次进入递归函数
• 如果上下左右都走不通，那就把节点(x,y)从当前可以走通的路径中pop掉，同时把(x,y)置为0

    这就是递归函数的四部分，可以发现，在这里面并没有进行return

• 走不通的情况，比如当前在(1,0)，向右可以走通进入(1,1)，但是(1,1)的上下左右都走不通，就pop了，同时(1,1)又变回了0，函数结束，也就实现了return。并且我们无需担心(1,0)点会再次向右试探，不停地pop,push陷入死循环，因为进入(1,0)向右试探，进入递归函数，函数结束后，它就自动顺序执行其他方向的试探了。也就是说走不通的路，一定不会被再次试探。由此确保，不return，也可以把所有的路径试探完。
• 能走通的情况，走通虽然进行了最短路径的更新，但是也没有进行return，我们还要寻找其他的最短路径。
• 那么已经走通的情况下如果不return会出现什么情况？在进行路径更新后，在终点，还会顺序执行对四个方向的试探(但是到达终点时候一定会是有方向，那个方向刚走过的节点值已经变成1，而向右向下是边界不能走，所以只剩一个方向可能走出去)。如果可以走出去，或许可能有一条路再次回到终点，但这条路是在上一条走通的道路的基础上进行的，肯定更长，最短路径不会被更新，同时就相当于回到了已经走通的情况。如果不能在此基础上走通，自然就不停地pop，就变成了上述走不通的情况了

AC代码：

#include<iostream>
#include<vector>
using namespace std;

struct Coordinate{
	int x;
	int y;
};
int matrix[1000][1000];
vector<Coordinate> current_step;
vector<Coordinate> best_step;

void Find_way(int x,int y);

int N,M; //代表行数和列数 
int main()
{
	while( cin>>N>>M ){
		current_step.clear();
		best_step.clear();
		for(int i=0; i<N; i++){
			for(int j=0; j<M; j++){
				cin>>matrix[i][j];
			}
		}
		
		Find_way(0,0);
		
		for(int i=0; i<best_step.size(); i++){
			cout<<"("<<best_step[i].x<<","<<best_step[i].y<<")"<<endl;
		} 
	}
} 
void Find_way(int x,int y)
{
	Coordinate c = {x,y};
	current_step.push_back(c); //假设当前节点是当前走向终点路线上的一点
	matrix[x][y] = 1;
	
	if( x==N-1&&y==M-1 ){ //当前路线走到了终点 
		if( best_step.empty()||current_step.size()<best_step.size() ){  //如果当前是第一次走通，或者是新找到的路径比之前找到的最短路径还要短，就进行替换 
			best_step = current_step; 
		} 
	} 
	
	if( x-1>=0&&matrix[x-1][y]==0 ){//向上可以走通
		Find_way(x-1,y);
	} 
	if( y-1>=0&&matrix[x][y-1]==0 ){//向左可以走通
		Find_way(x,y-1);
	}
	if( x+1<N&&matrix[x+1][y]==0 ){//向下可以走通
		Find_way(x+1,y);
	}
	if( y+1<M&&matrix[x][y+1]==0 ){//向右可以走通
		Find_way(x,y+1);
	}
	
	current_step.pop_back();
	matrix[x][y]=0; //当前节点走不下去，就返回上一个节点 
}