用深度优先搜索

1. 问题表述：
   1 1 2 1
   1 1 1 1
   1 1 2 1
   1 2 1 1
   1 1 1 2
   如图为一个5行4列的迷宫，图中1代表空格（可通行路径），2代表障碍物，问从起点到终点的最短路径是多少？只需输出一个步数

2. 输入形式为：
   5 4
   1 1 2 1
   1 1 1 1
   1 1 2 1
   1 2 1 1
   1 1 1 2
   1 1 4 3
   第一行为输入的迷宫的行数5和列数4
   最后一行为起点（1,1），终点（4,3）

3. 输出形式为：
   7

以下是代码（C++编写）：

#include 
using namespace std;//切记标准导入头文件模版 

//用深度优先搜索来求迷宫的最短路径； 
int m,n,ex,ey;//定义迷宫的边界和起点和终点 
int mp[100][100];//记录迷宫地图,1代表空地，2代表障碍 
int step=0,mi=9999;//定义步数和最小步数  
int vis[100][100]={0};//记录该点是否已经访问过,0代表未访问，1代表已访问 
//定义方向数组dx dy 
int dx[4]={1,0,-1,0};//按照右下左上的顺序走,迷宫左上角坐标为(1,1) 
int dy[4]={0,1,0,-1};

void dfs(int x,int y,int step){
	if(x==ex&&y==ey){//判断是否已经到达终点,即设置一个递归的出口 
		if(step<mi){//把最小步数更新； 
			mi=step;
		}
		return;//进行回溯 
	}
	
	for(int i=0;i<4;i++){//按照右下左上顺序依次走 
		int nx=x+dx[i];//下一步走到的位置 
		int ny=y+dy[i];
		if(mp[nx][ny]==1&&vis[nx][ny]==0){//下一步的到达的点为空地，且未访问过 
			vis[nx][ny]=1;//标记为已访问 
			dfs(nx,ny,step+1);//继续从下一点开始深度优先搜索
			vis[nx][ny]=0;//搜索到终点后进行回溯，把该点设置为未访问 
		}		
	}
	return;	
}

int main(){
	scanf("%d %d",&m,&n);//接收边界 
	for(int i=1;i<=m;i++){//输入迷宫地图坐标 
		for(int j=1;j<=n;j++){
			scanf("%d",&mp[i][j]);
		}
	}
	int sx,sy;
	scanf("%d %d %d %d",&sx,&sy,&ex,&ey);	//接收起点终点坐标 
	//开始时步数为0 
	vis[sx][sy]=1;//将起点设置为已访问 
	dfs(sx,sy,step);
	
	printf("%d",mi);//调用完深度优先搜索后直接输出最短步数	
	return 0; 
}

输入：

5 4
1 1 2 1
1 1 1 1
1 1 2 1
1 2 1 1
1 1 1 2
1 1 4 3

输出

7