C语言实现，找出迷宫起点到终点的最短路径，最详细的DFS教程

最短路径，最详细的DFS教程"/>

C语言实现，找出迷宫起点到终点的最短路径，最详细的DFS教程

今天下午学了下DFS的算法，然后输出一下我学到的。

求出迷宫中的最短路径:
测试数据:
结果是7
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

一共有两个，一个是未改进的，但是更容易理解，理解了第一个之后，可以更好的理解第二个优化的。

尝试移动的方向，当开始移动时，坐标的变化。

未优化

/*输入m行,n列数据,p,q表示终点,min表示最短路径
*/
int m, n, p, q;
int min = 999999999;
int a[100][100]; //1表示空,2表示障碍
int v[100][100]; //0表示未访问,1表示访问void dfs(int x, int y, int step)
{//判断是否是终点,并将走过的最短路径返给minif(x == p && y == q){if(step < min)min = step;return;	}	/*开始尝试进行移动,移动的顺序是右,下,左,上尝试,当一条路不通或者到终点时,进行回溯,关于坐标的位置,可以参考上述的图片进行理解.*///右 if(a[x+1][y] == 1 && v[x+1][y] == 0) {//当经过之后,将经过的坐标改为已访问v[x+1][y] = 1;dfs(x+1, y, step+1);//进行回溯时,将访问的坐标重置//防止其他路线需要经过时无法访问v[x+1][y] = 0; }//下if(a[x][y-1] == 1 && v[x][y-1] == 0) {v[x][y-1] = 1;dfs(x, y-1, step+1);v[x][y-1] = 0;}//左 if(a[x-1][y] == 1 && v[x-1][y] == 0) {v[x-1][y] = 1;dfs(x-1, y, step+1);v[x-1][y] = 0; }//上 if(a[x][y+1] == 1 && v[x][y+1] == 0) {v[x][y+1] = 1;dfs(x, y+1, step+1);v[x][y+1] = 0;}return;
}main()
{int i, j;//定义起点坐标int startx,starty;//定义数组的行和列 scanf("%d%d",&m,&n);//给地图赋值 for(i = 1; i <= m; i++){for(j = 1; j <= n; j++){scanf("%d",&a[i][j]);}}//定义起点和终点 scanf("%d%d%d%d",&startx,&starty,&p,&q);//将起点坐标设为访问v[startx][starty]  = 1; dfs(startx,starty,0);printf("%d",min);return 0;
}
//以上是详细的步骤,看明白后,下边优化的代码就很容易理解了

优化后

继以上坐标图，将坐标图化为实际的数据。

int m, n, p, q, k; 
int min = 99999;
int a[100][100];//1表示空,2表示障碍 
int v[100][100];//0表示未访问,1表示访问 
//迷宫问题
void dfs(int x, int y, int step) 
{//将具体的移动方向转化为数据,4个方向int dx[4] = {1, 0, -1, 0};int dy[4] = {0, -1, 0, 1};//判断终点if(x == p && y == q){if(step < min){min = step;}return;}//开始进行移动for(k = 0; k <= 3; k++){int tx,ty;//现在的坐标位置tx = x + dx[k];ty = y + dy[k];if(a[tx][ty] == 1 && v[tx][ty] == 0){v[tx][ty] = 1;dfs(tx,ty,step+1);v[tx][ty] = 0;}}return;
}main()
{//为地图赋值int i, j;scanf("%d%d",&m,&n);for(i = 1; i <= m; i++){for(j = 1; j <= n; j++){scanf("%d", &a[i][j]);}}int startx,starty;//确定起点和终点scanf("%d%d%d%d",&startx, &starty,&p,&q);//将起点设置已访问a[startx][starty] = 1;dfs(startx,starty,0);printf("%d",min);return 0;
}