DFS ( C++ )_c++中dfs(1,1,0,0)

作者：喵喵爱编程 | 2024-08-08 19:32:44

踩

c++中dfs(1,1,0,0)

7.12

#include<bits/stdc++.h>
using namespace std;

bool _m[51][51];
bool _flag[2600];
bool _path[51][51];

struct {
    int x;
    int y;

} order[2600];

int p,q;
int n,m;

int minn=2600;

int _next[4][2]= {{1,0},{0,1},{-1,0},{0,-1}};

void dfs(int step, int x, int y) {
    if(x==p-1&&y==q-1) {
        if(step<minn) minn=step;
        _path[0][0]=1;
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                if(_m[i][j]) {
                    printf("@ ");
                } else {
                    if(i==p-1&&j==q-1) {
                        printf("# ");
                    } else {
                        printf("%d ",_path[i][j]);
                    }

                }
            }
            putchar('\n');
        }
        putchar('\n');

        for(int i=0; i<step; i++) {
            printf("%d %d\n",order[i].x,order[i].y);
        }
        putchar('\n');
        putchar('\n');
    }
    int tmpx,tmpy;
    for(int i=0; i<4; i++) {
        tmpx=x+_next[i][0];
        tmpy=y+_next[i][1];
        if(!_path[tmpx][tmpy]&&(tmpx>=0&&tmpx<n)&&(tmpy>=0&&tmpy<m)&&!_m[tmpx][tmpy]) {
            _path[tmpx][tmpy]=1;
            order[step].x=tmpx;
            order[step].y=tmpy;
            dfs(step+1,tmpx,tmpy);
            _path[tmpx][tmpy]=0;
        }
    }
    return ;
}

int main() {
    order[0].x=0;
    order[0].y=0;
    while(~scanf("%d%d",&n,&m)) {
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                scanf("%d",&_m[i][j]);
            }
        }
        scanf("%d%d",&p,&q);
        dfs(1,0,0);

        printf("way = %d\n",minn);
    }
    return 0;
}

/*

5 4
0 0 1 0
0 0 0 0
0 0 1 0
0 1 0 0
0 0 0 1
4 3

10 10
0 0 0 0 1 0 1 0 1 0
0 1 0 1 0 0 1 0 1 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 1 1 1 0 1 1
0 1 0 1 0 0 1 0 1 0
0 0 0 0 1 0 0 0 0 0
0 0 1 0 1 1 1 0 1 1
0 1 0 1 0 0 1 0 1 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 1 0 1 1
6 6
*/

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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103

7.13

#include<bits/stdc++.h>
using namespace std;

bool _m[51][51];
bool _flag[2600];
int _path[51][51];

struct {
    int x;
    int y;

} order[2600];

int p,q;
int n,m;

int minn=2600;

int _next[4][2]= {{1,0},{0,1},{-1,0},{0,-1}};

void dfs(int step, int x, int y) {
    if(x==p-1&&y==q-1) {
        if(step<minn) minn=step;
        _path[0][0]=1;
        putchar('\n');
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                if(_m[i][j]) {
                    printf("@ ");
                } else {
                    if(i==p-1&&j==q-1) {
                        printf("# ");
                    } else {
                        printf("%d ",_path[i][j]);
                    }

                }
            }
            putchar('\n');
        }
        putchar('\n');

        for(int i=0; i<step; i++) {
            printf("%d %d\n",order[i].x,order[i].y);
        }
        putchar('\n');
        putchar('\n');
    }
    int tmpx,tmpy;
    for(int i=0; i<4; i++) {
        tmpx=x+_next[i][0];
        tmpy=y+_next[i][1];
        if(!_path[tmpx][tmpy]&&(tmpx>=0&&tmpx<n)&&(tmpy>=0&&tmpy<m)&&!_m[tmpx][tmpy]) {
            _path[tmpx][tmpy]=step+1;
            order[step].x=tmpx;
            order[step].y=tmpy;
            dfs(step+1,tmpx,tmpy);
            _path[tmpx][tmpy]=0;
        }
    }
    return ;
}

int main() {
    order[0].x=0;
    order[0].y=0;
    while(~scanf("%d%d",&n,&m)) {
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                scanf("%d",&_m[i][j]);
            }
        }
        scanf("%d%d",&p,&q);
        dfs(1,0,0);

        printf("way = %d\n",minn);
    }
    return 0;
}

/*

5 4
0 0 1 0
0 0 0 0
0 0 1 0
0 1 0 0
0 0 0 1
4 3

10 10
0 0 0 0 1 0 1 0 1 0
0 1 0 1 0 0 1 0 1 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 1 1 1 0 1 1
0 1 0 1 0 0 1 0 1 0
0 0 0 0 1 0 0 0 0 0
0 0 1 0 1 1 1 0 1 1
0 1 0 1 0 0 1 0 1 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 1 0 1 1
6 6
*/

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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104

#include<bits/stdc++.h>
using namespace std;

bool _m[51][51];
bool _flag[2600];
int _path[51][51];

struct {
    int x;
    int y;

} order[2600];

int p,q;
int n,m;

int minn=2600;

int _next[4][2]= {{1,0},{0,1},{-1,0},{0,-1}};

void dfs(int step, int x, int y) {
    if(x==p-1&&y==q-1) {
        if(step<minn) minn=step;
        _path[0][0]=1;
        printf("\n------------------------\n");
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                if(_m[i][j])  printf("@ ");
                else {
                    if(i==p-1&&j==q-1) printf("# ");
                    else printf("%d ",_path[i][j]);
                }
            }
            putchar('\n');
        }
        putchar('\n');

        for(int i=0; i<step; i++) printf("%d %d\n",order[i].x,order[i].y);
        printf("------------------------\n");
    }
    int tmpx,tmpy;
    for(int i=0; i<4; i++) {
        tmpx=x+_next[i][0];
        tmpy=y+_next[i][1];
        if(!_path[tmpx][tmpy]&&(tmpx>=0&&tmpx<n)&&(tmpy>=0&&tmpy<m)&&!_m[tmpx][tmpy]) {
            _path[tmpx][tmpy]=step+1;
            order[step].x=tmpx;
            order[step].y=tmpy;
            dfs(step+1,tmpx,tmpy);
            _path[tmpx][tmpy]=0;
        }
    }
    return ;
}

int main() {
    order[0].x=0;
    order[0].y=0;
    while(~scanf("%d%d",&n,&m)) {
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                scanf("%d",&_m[i][j]);
            }
        }
        scanf("%d%d",&p,&q);
        dfs(1,0,0);
        printf("way = %d\n",minn-1);
    }
    return 0;
}

/*

5 4
0 0 1 0
0 0 0 0
0 0 1 0
0 1 0 0
0 0 0 1
4 3

10 10
0 0 0 0 1 0 1 0 1 0
0 1 0 1 0 0 1 0 1 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 1 1 1 0 1 1
0 1 0 1 0 0 1 0 1 0
0 0 0 0 1 0 0 0 0 0
0 0 1 0 1 1 1 0 1 1
0 1 0 1 0 0 1 0 1 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 1 0 1 1
6 6
*/

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
88
89
90
91
92
93
94
95

8.15

#include<bits/stdc++.h>
using namespace std;

const int N=1000;

int n,m;
int x,y;

int _m[N][N];
int _path[N][N];
int _way[N][2];

int idx=1;

int _next[4][2]= {{1,0},{0,1},{-1,0},{0,-1}};

void dfs(int a, int b, int step) {
    if(a==x-1&&b==y-1) {
		cout<<"\n";
		cout<<"\n------------------------\n";
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                if(_m[i][j]==1) cout<<"@ ";
                else {
					if(i==x-1&&j==y-1) cout<<"# ";
					else cout<<_path[i][j]<<" ";
                }
            }
            cout<<"\n";
        }
        cout<<"\n";
        for(int i=0;i<step;i++) cout<<_way[i][0]+1<<" "<<_way[i][1]+1<<"\n";
		cout<<"\n------------------------\n";

        return ;
    }

    int tmpa, tmpb;
    for(int i=0; i<4; i++) {
        tmpa=a+_next[i][0];
        tmpb=b+_next[i][1];

        if(tmpa<0||tmpb<0||tmpa>=n||tmpb>=m) continue;
        if(!_path[tmpa][tmpb]&&!_m[tmpa][tmpb]) {
            _path[tmpa][tmpb]=step+1;
            _way[step][0]=tmpa;
            _way[step][1]=tmpb;
            dfs(tmpa, tmpb, step+1);
            _path[tmpa][tmpb]=0;
        }
    }

    return ;
}

int main() {

    cin>>n>>m;
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++) cin>>_m[i][j];
    cin>>x>>y;
    _path[0][0]=1;

    dfs(0,0,1);

    return 0;
}

/*

5 4
0 0 1 0
0 0 0 0
0 0 1 0
0 1 0 0
0 0 0 1
4 3

*/

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

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/喵喵爱编程/article/detail/949607