搜索

有关DFS的算法和练习题整体的归纳与总结

DFS

算法理解

递归思想：终止条件，循环，有效条件，走过标记；

eg.

hduoj1010

典型迷宫，从初始点出发，四个方向，分别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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>

using namespace std;
char maze[10][10];
int flag[10][10];//判断是否走过标记
int dir[4][2]={0,1,1,0,0,-1,-1,0};//四个方向
int dx,dy,sx,sy;//门和开始的位置
int N,M,T;
bool flaga=false;

void dfs(int x,int y,int step)
{
    if(x==dx&&y==dy){
        if(step==T)flaga=true;
        return;
    }
    if(step>=T)return;
    if(maze[x][y]!='X'){
    for(int i=0;i<4;i++){
        int nowx=dir[i][0]+x;
        int nowy=dir[i][1]+y;
        if(nowx<0||nowy<0||nowx>=N||nowy>=M)continue;//跳过越界
        if(flag[nowx][nowy]==0&&maze[nowx][nowy]!='X'){
            flag[nowx][nowy]=1;
            dfs(nowx,nowy,step+1);
            flag[nowx][nowy]=0;
            if(flaga)return;
        }
    }
    }
}

int main()
{
    while(scanf("%d %d %d",&N,&M,&T)&&N!=0&&M!=0&&T!=0){
        memset(flag,0,sizeof(flag));
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                cin>>maze[i][j];
                if(maze[i][j]=='S'){
                    sx=i;
                    sy=j;
                }
                if(maze[i][j]=='D'){
                    dx=i;
                    dy=j;
                }
            }
        }
        /*for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                cout<<maze[i][j];
            }
            cout<<endl;
        }*/
        // 不可大于最短路径||奇偶剪枝：若绕路必定比最短路径增长偶数time
        if(abs(sx-dx)+abs(sy-dy)>T||(sx+sy+dx+dy+T)%2==1)cout<<"NO"<<endl;
        else
        {
            flaga=false;
            flag[sx][sy]=1;
        dfs(sx,sy,0);
        //printf("%d\n",m);
        if(flaga)cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
        }
    }
    return 0;
}
/*
3 4 5
S.X.
..X.
...D
*/

hduoj1016

质数圈
1-n内的数字放置在圈内，使相邻2个数字和为质数；

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

using namespace std;

int in[25];
int flag[25];
bool prime[45];
int res[25];
int n;

//预处理判断40内的质数
void Prime()
{
    for(int i=3;i<=40;i++){
        bool flag=false;
        for(int j=2;j<=sqrt(i);j++){
            if(i%j==0){
                flag=true;
                break;
            }
        }
        if(flag){
            prime[i]=false;
        }
        else prime[i]=true;
    }
}

//输出
void Output()
{
    for(int i=0;i<n;i++){
        cout<<res[i];
        if(i!=n-1)cout<<" ";
    }
    cout<<endl;
}
int count=0;
void dfs(int x,int step)
{
    if(step==n){
        //判断与头相加是否为素数
        if(prime[1+res[step-1]]){
            Output();
        }
        return;
    }
    int a=in[x];
    for(int i=0;i<n;i++){
        int b=in[i];//cout<<a<<" "<<b<<endl;
        if(flag[i]==0&&prime[a+b]){//还未走过的位置,并且满足条件
            //继续走下去
            flag[i]=1;
            res[step]=in[i];
            dfs(i,step+1);
            flag[i]=0;
        }
    }
    return;
}


int main()
{
    int Case=0;
    Prime();
    prime[2]=1;
    while(scanf("%d",&n)!=EOF&&n!=0){
        memset(in,0,sizeof(in));
        memset(flag,0,sizeof(flag));
        Case++;
        for(int i=0;i<n;i++){
            in[i]=i+1;
        }
        flag[0]=1;
        res[0]=in[0];

        cout<<"Case "<<Case<<":"<<endl;
        dfs(0,1);
        cout<<endl;
    }
    return 0;
}

hduoj1312

Red and Black 计算从start开始的所有路径，路径上经过的不重复的.数量

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
 #include <iostream>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

using namespace std;

char datamap[25][25];
int flag[25][25];
int ff[25][25];
int dir[4][2]={-1,0,0,1,1,0,0,-1};
int sx,sy;
int count;
int w,h;

//计算从start开始的所有路径，路径上经过的不重复的.数量
void dfs(int x,int y)
{
    for(int i=0;i<4;i++){
        int tmpx=x+dir[i][0];
        int tmpy=y+dir[i][1];
        //不是红砖，并且在范围内,并且没走过
        if(datamap[tmpx][tmpy]=='.'&&tmpx>=0&&tmpx<h&&tmpy>=0&&tmpy<w&&!flag[tmpx][tmpy]){
            flag[tmpx][tmpy]=1;
           // cout<<count<<endl;
            count++;
            dfs(tmpx,tmpy);

        }
    }
    return;
}


int main()
{
    while(scanf("%d %d",&w,&h)!=EOF&&w!=0&&h!=0){
        count=1;
        memset(flag,0,sizeof(flag));
        memset(ff,0,sizeof(ff));
        for(int i=0;i<h;i++){
            for(int j=0;j<w;j++){
                cin>>datamap[i][j];
                if(datamap[i][j]=='@'){
                    sx=i;
                    sy=j;
                }
            }
        }
        dfs(sx,sy);
        cout<<count<<endl;

      /* for(int i=0;i<h;i++){
            for(int j=0;j<w;j++){
                cout<<datamap[i][j];
            }
            cout<<endl;
        }*/
    }
    return 0;
}