dfs基本模型：
1.使用深搜来进行全排列
其中的book数组来存放是否已经存在之前放进a数组中的数
a数组用来存放每一次的结果
#include <stdio.h> int n; int a[10],book[10]; //c语言中全局变量没有赋值以前为0 void dfs(int step) //深搜 { int i; if(step==n+1){ //这里是到最后的时候 for(i=1;i<=n;i++) printf("%d ",a[i]); printf("\n"); return; //此时设置出口出去 } for(i=1;i<=n;i++){ if(book[i]==0){ a[step] = i; book[i]=1; dfs(step+1); //这里通过调用自身 book[i] = 0; } } } int main() { scanf("%d",&n); dfs(1); return 0; }
深搜实际上来说就是找一个方向找到底，再进行别的方向找到底，直至最后
——————————————————————————————————————
2.使用深搜找到最短位置，地图
本题要求是求出初始位置到达目标位置的最短距离
输入条件：
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
第一行是5行四列
中间到最后一列之前是地图，0代表无障碍物，1代表有障碍物
最后一行是初始位置(1,1) 目标位置为(4,3)
#include <stdio.h> int n,m,p,q,min=9999999; 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}}; int i,tx,ty; if(x==p&&y==q){ //到达终点 if(step<min) min = step; return; //找到的话就结束 } for(i=0;i<4;i++){ tx = x+next[i][0]; //tx，ty分别为向一个方向走 ty = y+next[i][1]; if(tx<1||tx>m||ty<1||ty>n) continue; if(a[tx][ty]==0&&book[tx][ty]==0){ //不是障碍物或者之前已经走过的路径 book[tx][ty]=1; //提前说明这个已经走过了 dfs(tx,ty,step+1); //进行深搜 book[tx][ty]=0; //保存原来的点 } } } int main() { int i,j,startx,starty; scanf("%d%d",&n,&m); //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] = 1; dfs(startx,starty,0); //其中包括起始位置和步数 //输出最短步数 printf("%d",min); return 0; }
运行结果为：7
解决思路：
1.找到最短路径那就需要把各个方向位置都去走过一遍，最后才能求出最短的距离(因为是深搜，所以必须把所有的路径都求过去)
2.本题需要两个数组，一个用来存放地图，另一个存放的是方向，本题代码中next就是存放的是方向，4行每一行代表x和y分别加多少，就是上下左右四个方向
3.dfs应当有三个条件，两个是x和y，另外一个就是步数，用来求最短的步数
4.就是判断是否出界的条件，还有就是是否当前是障碍物和曾经走过的位置
5.走到最后终点进行最小值的比对，进而求出最短路径
——————————————————————————————————————
