cdoj 15 Kastenlauf dfs

题目链接:

http://acm.uestc.edu.cn/#/problem/show/15

题意:

n+2个点，要求每个点之间的距离小于等于1000就可以走过去，然后问你能否从1走到n+2

题解:

dfs

代码:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 #define MS(a) memset(a,0,sizeof(a))
 5 #define MP make_pair
 6 #define PB push_back
 7 const int INF = 0x3f3f3f3f;
 8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
 9 inline ll read(){
10     ll x=0,f=1;char ch=getchar();
11     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
12     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
13     return x*f;
14 }
15 //////////////////////////////////////////////////////////////////////////
16 const int maxn = 1e5+10;
17 
18 struct node{
19     int x,y;
20 }a[105];
21 
22 int n,f,vis[105];
23 
24 void dfs(int u){
25     if(vis[u]) return ;
26     vis[u] = 1;
27     for(int i=1; i<=n; i++){
28         if(i==u)
29             continue;
30         if(abs(a[i].x-a[u].x) + abs(a[i].y-a[u].y) <= 1000)
31             dfs(i);
32     }
33 }
34 
35 int main(){
36     int T=read();
37     while(T--){
38         MS(vis);
39         f = 1;
40         n = read(); 
41         n += 2;
42         for(int i=1; i<=n; i++)
43             a[i].x=read(),a[i].y=read();
44         dfs(1);
45         if(vis[n]) puts("happy");
46         else puts("sad");
47 
48     }
49 
50     return 0;
51 }