dfs求迷宫的最短路径（有障碍物）

题目：小迷突然有一天想去玩迷宫，迷宫表现为一个n×m 的网格，网格上只有两种情况: 无障碍物和障碍物。
如果他在坐标为 (i,j) 的网格里，他可以选择 (i+1,j),(i,j+1),(i−1,j),(i,j−1） 四个方向行走，小迷想知道走出迷宫的最短路径是多少，如果走不出去输出-1；

输入：第一行两个整数 n,m(1≤n,m≤2000)；
           第二行四个整数sx,sy,ex,ey(1≤sx,ex≤n,1≤sy,ey≤m) 表示起点与终点的坐标；

 输出：一行一个整数，表示最短距离，若出不去输出-1；

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[1000][1000];//用数组去表示迷宫 
int b[1000][1000];//标记数组 
int v=999999;//初始化步数，的得到最小的步数 
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};//表示向上下左右四个方向移动 
void dfs(int x1,int y1,int x2,int y2,int step){
	if(x1==x2&&y1==y2) {//如到达了终点坐标，去判断这条路走的是否比之前走的路径要小 
		if(step<v){
			v=step;
		} 
		return;
	}
	for(int i=0;i<=3;i++){//上下左右四个方向依次遍历 
		int tx=x1+dx[i];
		int ty=y1+dy[i];
		if(tx<1||tx>n||ty<1||ty>m)	continue;//表示超出了迷宫的边界，就不进行遍历 
		if(a[tx][ty]==0&&b[tx][ty]==0){//表示这一格无障碍物且没被标记 
			b[tx][ty]=1;//标记一下这个位置被走过 
			dfs(tx,ty,x2,y2,step+1);
			b[tx][ty]=0;//回溯 
		}
	}
	return ; 
} 
int main(){
	cin>>n>>m;//表示迷宫大小n*m 
	int ax,ay,ex,ey;
	cin>>ax>>ay>>ex>>ey;// 表示起始和结束的坐标 
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];//1表示有障碍物，0表示无障碍物 
		}
	}
	dfs(ax,ay,ex,ey,0);//广度优先遍历 
	b[ax][ay]=1;
	printf("这个迷宫的最短路径:"); 
	v==999999?cout<<-1:cout<<v;
	return 0;
}