理解深度优先搜索的关键在于解决“当下该如何做”。至于“下一步该如何做”则与“当下该如何做”是一样的。
基本模型：
void dfs(int step)
{
判断边界
尝试每一种可能 for(i=1;i<=n;i++)
{
继续下一步 dfs(step+1)
}
返回
}
//或者是
int dfs(int t)
{
if(满足输出条件)
{
输出解;
}
for(int i=1;i<=尝试方法数;i++)
if(满足进一步搜索条件)
{
为进一步搜索所需要的状态打上标记;
dfs(t+1);
恢复到打标记前的状态;//也就是说的{回溯一步}
}
}示例1：输入整数n,全排列1~n
#include "stdio.h"
int a[10],book[10],n;
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);
printf("\n");
book[i]=0;
}
}
return;
}
int main(){
scanf("%d",&n);
dfs(1);
return 0;
}示例2：□ □ □ + □ □ □ = □ □ □，在□中填入1~9使等式成立且每位数字只出现一次
#include "stdio.h"
int a[10],book[10],sum=0;
void dfs(int step){
int i;
if(step==10){
if(a[1]*100+a[2]*10+a[3]+a[4]*100+a[5]*10+a[6]==a[7]*100+a[8]*10+a[9]){
sum++;
printf("%d%d%d+%d%d%d=%d%d%d ",a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9]);
}
return;
}
for(i=1;i<=9;i++){
if(book[i]==0){
a[step]=i;
book[i]=1;
dfs(step+1);
book[i]=0;
}
}
return;
}
int main(){
dfs(1);
printf("\n");
printf("一共有%d组结果",sum/2);
}示例3：迷宫。
给定一个N*M方格的迷宫，迷宫里有T处障碍，障碍处不可通过。给定起点坐标和终点坐标，问: 每个方格最多经过1次，有多少种从起点坐标到终点坐标的方案。在迷宫中移动有上下左右四种方式，每次只能移动一个方格。数据保证起点上没有障碍。
#include "stdio.h"
int m,n,p,q,min=99999,sum=0;
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 tx,ty,k;
//判断是否到达位置
if(x==p&&y==q){
if(step<min){
sum++;
min=step;
}
return;//很重要
}
//枚举4种走法
for(k=0;k<=3;k++){
//计算下一个点坐标
tx=x+next[k][0];
ty=y+next[k][1];
//判断是否越界
if(tx<1||tx>n||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;
}
}
return ;
}
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条路径",sum)
printf("\n");
printf("最短路径走了%d步",min);
return 0;
}