（奶酪）简单理解C++的深度优先搜索_杰瑞爬进了奶酪的小洞c++

题目地址

我觉得这个题用来理解深搜还是非常好的

只给提示

1.我们知道杰瑞要进洞的话一定需要遍历所有可能从下表面进入的点

2.进入之后我们要找所有可能连通并且的点

3.最后状态是找到了可以出去的点

需要注意的地方
1.数据范围

2.深搜时我们需要对一个洞口进行多次探索吗？

为了方便阅读，我就不压行了，，每次都搞不懂题解压行的人想干啥，，，难道能显得自己更厉害吗？

#include <bits/stdc++.h>
#define ll long long
using namespace std;
double h,n,r,t,vex[1100][4];
bool falg;
int vis[1100];
double get_dis(ll x,ll y,ll z,ll i,ll j,ll k)
{
     return sqrt((x-i)*(x-i)+(y-j)*(y-j)+(z-k)*(z-k));
}

void DFS(int pos)
{
    if(vex[pos][3]>=(h-r))
    {
        falg=true;
        return;
    }
    vis[pos]=1;
    for(int i=1;i<=n;i++)
    {
        if((get_dis(vex[pos][1],vex[pos][2],vex[pos][3],vex[i][1],vex[i][2],vex[i][3])<=2*r)&&!vis[i])
        {
            DFS(i);
        }
    }
}
int main()
{
    for(cin>>t;t;t--)
    {
        cin>>n>>h>>r;
        falg=false;
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=n;i++)
            for(int j=1;j<=3;j++)
                   cin>>vex[i][j];
        for(int i=1;i<=n;i++)
        {
            if(!vis[i]&&vex[i][3]<=r)
            {
                DFS(i);
            }
            if(falg)
             break;
        }
         if(falg)
         {
             cout<<"Yes"<<endl;
         }
         else
            cout<<"No"<<endl;
    }
    return 0;
}

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