深度优先搜索

理解深度优先搜索的关键在于解决“当下该如何做”。至于“下一步该如何做”则与“当下该如何做”是一样的。
基本模型：

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;  
}