本文主要是介绍绝地逃生(DFS)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
假设你现在被困一个神秘山洞，在几经查探之后发现很难找到出路。幸运的是，你在山洞里乱走的时候捡到了一张地图。通过这张地图，你能判断自己是否能够走出这个山洞（假设不能走对角线）。但，身为程序员的你觉得看一张大地图找路实在是浪费精力，为了保存体力在山洞中生存下去，机智的你掏出随身携带的电脑写了一段程序，让这个程序来帮你找路。
地图由一个矩阵表示，矩阵的元素只含有0和1，1表示真，即那个点可以走，0表示假，即那个点是陷阱。你现在要实现的是寻找一条能够避开所有陷阱的路通往出口。假设你的初始位置是在矩阵的左上方第一个点，出口是在矩阵的右下方最后一个点。
Input
输入有多组数据。EOF结束
每组数据满足以下的格式
第一行为两个整数代表矩阵的行和列，row，col（0 < row,col <= 60）
接着有一个矩阵描述整张地图
Output
如果能够找到一条避开所有陷阱并且通往出口的路，输出YES
否则输出NO
#include <stdio.h>
int n;
int m;
int map[60][60];
int flag = 0;
void findroad(int row, int col) {if (!flag) {if (row == n - 2 && col == m - 1) {flag = 1;} else if (map[row][col + 1]) {findroad(row, col + 1);} else if (map[row + 1][col]) {findroad(row + 1, col);}}
}int main() {while (scanf("%d%d", &n, &m) != EOF) {for (int i = 0; i < n - 1; i++) {for (int j = 0; j < m; j++) {scanf("%d", &map[i][j]);}}flag = 0;findroad(0, 0);if (flag == 1) {printf("YES\n");} else {printf("NO\n");}flag = 0;}return 0;
}这篇关于绝地逃生(DFS)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
