第4章第2节-解救小哈

/迷宫最短路径问题，0表示可通过，1表示障碍物不能通过/
#include "stdio.h"
int n,m,p,q,min = 99999999;
int a[51][51],book[51][51];
void dfs(int x,int y,int step)
{
int next[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};//next为方向数组，分别代表向右，向下，向左，向上走
int tx,ty,k;
//判断是否到达终点
if(x == p && y == q)
{
//更新最小值
if(step < min)
{
min = step;
}
return;//请注意这的返回很重要
}

//依次遍历四种路径
从k=0开始一直到k=3执行循环操作
//计算目标坐标的位置
根据当前位置(x,y)加上预设步长数组next中的第k项元素得到新的候选坐标(tx, ty)
//判断候选坐标是否超出合法范围
如果候选坐标落在棋盘之外则跳过此次循环
//检查目标位置的状态
如果目标位置既不是障碍物也不是已访问过则进行下一步操作
//标记已访问并递归搜索后续路径
将当前候选位置标记为已访问随后立即进行深度优先搜索以探索更多可能性之后撤销当前标记以恢复初始状态

int main()
{
int i,j,startx,starty;
//读入n和m,n为行，m为列
scanf("%d%d",&n,&m);
//读入迷宫
for(i = 1;i <= n;i++)
{
for(j = 1; j <= m;j++)
{
scanf("%d",&a[i][j]);
}
}
//读入起点和终点坐标
scanf("%d %d %d %d",&startx,&starty,&p,&q);

//初始化路径上的起始位置
设定book[startx][starty] = true; //将路径上已访问的位置标记为true以避免重复访问
调用深度优先搜索算法函数 dfs(startx, starty, 0); //执行深度优先搜索遍历路径
其中：

• 第一个参数表示起始点的x坐标
• 第二个参数表示起始点的y坐标
• 第三个参数表示初始步数为0

//输出最短步数
printf("%d\n",min);
getchar();getchar();
return 0 ;
}
/*********
示例输入：
5 4
0 0 1 0
0 0 0 0
0 0 1 0
0 1 0 0
0 0 0 1
1 1 4 3
示例输出：
7
************/