迷宫最短路径问题（BFS、DFS）

一、迷宫最短路径问题

 　　给你一个m*n的迷宫，迷宫中有障碍物（1表示障碍物），你可以上下左右移动，但不能走走过的迷宫，给出指定的起点（x,y）和指定的终点（x_l,y_l）,求最短路径长度是多少，或者打印其中一个最短路径，

输入：nums={
0, 1, 0, 0, 0,
0, 1, 0, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 0, 0,
};
输出：最短路径长度：8
最段路径为： 1 0，2 0，3 0，4 0，4 1，4 2，4 3，4 4

思路：1.使用DFS深度优先遍历来到达终点的所有路径，选择最短的路径。
 　 　2.使用BFS层序遍历，一层一层往外扩张，使用结构体简化 *** 作

DFS

//***************************上下左右迷宫，有障碍物，DFS************************
 vector<int> dx = { -1,1,0,0 };
 vector<int> dy = { 0,0,-1,1 };
 vector<vector<int>> path;
 vector<vector<int>> res;
 void dfs(vector<vector<int>> nums,int x,int y,int x_l,int y_l) {
	 if (x == x_l && y == y_l) {                                   
		if (res.size() == 0 || res.size() > path.size()) res = path;  //更新最短路径
		 return;
	 }
	 for (int i = 0; i < 4; i++) {                                    //上下左右
		 int x_currt = x + dx[i];
		 int y_currt = y + dy[i];
		 if (x_currt < 0 || x_currt >= nums.size() || y_currt < 0 || y_currt>=nums[0].size()  //边界条件，障碍物，已经走过
			 || nums[x_currt][y_currt] == -1 || nums[x_currt][y_currt] == 1) continue;
		 nums[x_currt][y_currt] = -1;
		 path.push_back({ x_currt ,y_currt });
		 dfs(nums, x_currt, y_currt, x_l, y_l);       
		 path.pop_back();
	 }
 }

BFS

//***************************上下左右迷宫，有障碍物，BFS**********************
//使用队列辅助，每层出栈时，把下层的压栈。
 class P {
 public:
	 int x;  //横坐标
	 int y;  //纵坐标
	 int len; //路径长度
	 vector<vector<int>> path; //记录路径
 };
 void bfs(vector<vector<int>> nums, int x, int y, int x_l, int y_l) {
	   queue<P> que;                 //用队列记录每个结构体在每层的路径和路径长度，这样同一层的点的路径长度是相同的。
	   vector<vector<int>> path;
	   P currt;
	   currt.x = x;
	   currt.y = y;
	   currt.len = 0;
	   currt.path = path;
	   que.push(currt);   //入队
	   while (!que.empty()) {
			   currt = que.front();   //d出队首结点
			   que.pop();    
			   if (currt.x == x_l && currt.y == y_l) {             //如果这一层是终点则退出遍历
				   cout << "最短路径长度："<<currt.len << endl;    //输出最短路径长度
				   for (int i = 0; i < currt.path.size(); i++)    //输出路径
					   cout << currt.path[i][0] << " " << currt.path[i][1] << endl;
				   return;
			   }
			   for (int i = 0; i < 4; i++) {    //上下左右
				   int x_currt = currt.x + dx[i];
				   int y_currt = currt.y + dy[i];
				   if (x_currt < 0 || x_currt >= nums.size() || y_currt < 0 || y_currt >= nums[0].size()  //判断边界条件和障碍以及走过
					   || nums[x_currt][y_currt] == -1 || nums[x_currt][y_currt] == 1)  continue;
				   P next;
				   next.x = x_currt;
				   next.y = y_currt;
				   next.len = currt.len + 1;
				   next.path = currt.path;
				   next.path.push_back({ x_currt ,y_currt}); 
				   que.push(next);                  //把下一层的点压入队列
				   nums[x_currt][y_currt] = -1;    //标记走过的路
			   }
	   }
	   return ;

 }