DFS入门

DFS

DFS，即深度优先搜索，是最重要的搜索思想之一，其核心在于解决当下问题，而下一步的做法和当前一样。其基本模型如下：

1
2
3
4
5
6
7
8
9
10
void dfs(int step)
{
    判断边界
    for(int i=;i<=n;i++)
    {
        //解决当下问题    
        dfs(step+1);
    }
    return ;
}

dfs之数的全排列

题目大意

给定一个正整数n(n<10),写出1~n的全排列

解题思路

利用dfs基本模型来逐步解决

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <cstdio>
int a[10]={0},book[10]={0},n;
void dfs(int step)
{
    if(step>=n+1)
    {
        for(int i=1;i<=n;i++) printf("%d",a[i]);
        printf("\n");
        return ;
    }
    for(int i=1;i<=n;i++)
    {
        if(book[i]==0)
        {
            a[m]=i;
            book[i]=1;
            dfs(step+1);
            book[i]=0;
        }
    }
    return ;
}
int main()
{
    scanf("%d",&n);
    dfs(1);
    return 0;
}

dfs之迷宫搜索

题目大意

给定一个n行m列迷宫，要求从寻找从起点到终点的最短路径

解题思路

直接使用dfs搜索找出最短路径

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<cstdio>
int startX,startY,endX,endY,min=99999;
int a[51][51]={0},book[51][51]=0;
void dfs(int x,int y,int step)
{
    if(x==endX&&y==endY)
    {
        if(step<min) min=step;
        return;
    }
    int next[4][2]={
        {1,0},{0,1},{-1,0},{0,-1}
    }
    int tx,ty;
    for(int i=0;i<=3;i++)
    {
        tx=x+next[i][0];
        ty=y+next[i][1];
        if(tx<1||ty<1||tx>n||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()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&a[i][j]);
    scanf("%d%d%d%d",&startX,&startY,&endX,&endY);
    book[startX][startY]=1;
    dfs(startX,startY,0);
    printf("%s%d","最少步数为：",min);
    return 0;
}