解救小哈 【啊哈算法—解救小哈（深度优先搜索）】小哈在一个（m * n)大小的迷宫（0 ? m, n ? 50）里迷路了。在迷宫中，每个单元格要么是空地，要么是障碍物。现在要找到从起点到小哈位置的最短步数。
思路：
使用递归一步一步向前试探，试探成功则步数加一，返回后向另一个方向试探，到达终点后比较最小步数。
源码：
#includeint n, m, p, q, min = _CRT_INT_MAX;
int a[51][51], book[51][51];
void dfs(x, y, step);
void dfs(x, y, step) {
int next[4][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };
//控制下一步走的方向
int tx, ty;
//下一步坐标
int k;
if (x == p && y == q) {//到达终点
if (step < min) {
min = step;
//更新最小值
}
return;
} for (k = 0;
k < 3;
k++) {//循环尝试下一步
tx = x + next[k][0];
ty = y + next[k][1];
if (tx < 1 || tx > n || ty < 1 || ty > m) {//判断是否出界
continue;
}
if (a[tx][ty] == 0 && book[tx][ty] == 0) {//判断是否为障碍物或已走过
book[tx][ty] = 1;
//标记此格已走过
dfs(tx, ty, step + 1);
book[tx][ty] = 0;
//取消尝试
}
}
return;
}int main() {
int i, j;
int startx, starty;
printf("请输入迷宫大小\n");
scanf("%d %d", &n, &m);
//输入迷宫大小 printf("请输入迷宫\n");
for (i = 1;
i <= n;
i++) {//输入迷宫
for (j = 1;
j <= m;
j++) {
scanf("%d", &a[i][j]);
}
} printf("请输入终点：");
scanf("%d %d", &p, &q);
//输入终点； printf("请输入起点：");
scanf("%d %d", &startx, &starty);
dfs(startx, starty, 0);
printf("最小路径：%d", min);
return 0;
}
推荐阅读
- Linux服务器开发|记录一次腾讯c/c++ linux后台开发岗面试经历（面试题含答案）
- python|wasm转c调用实战
- ubuntu|ubuntu系统下gcc命令的执行与Makefile的简单使用
- ubuntu|Ubuntu系统里使用gcc和Makefile编译c程序
- 嵌入式开发|ubuntu下使用gcc和Makefile执行c程序
- 数据结构|课程设计(飞机订票系统) 超全
- C语言|初级指针详解
- C语言|动态内存管理与柔性数组
- 嵌入式C语言强化学习——（嵌入式学习路线1）