csu 1460: Kastenlauf，csu1460kastenlauf

csu 1460: Kastenlauf，csu1460kastenlauf

1460: Kastenlauf

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 90 Solved: 28
[Submit][Status][Web Board]

Description

Input

Output

Sample Input

2
2
0 0
1000 0
1000 1000
2000 1000
2
0 0
1000 0
2000 1000
2000 2000

Sample Output

happy
sad

题意：每走50米喝一次，身上带最多只够喝20次，只要能走到商店就补足到20次。  现给n+2个点，起点 ，n个商店  和终点。

#include<stdio.h>
#include<queue>
#include<iostream>
using namespace std;
typedef struct nnn
{
    int x,y;
}NODE;
int n;
NODE node[105];
int abs(int a)
{
    return a>0?a:-a;
}
int bfs()
{
    queue<NODE>q;
    NODE p;
    int vist[105]={0};
    q.push(node[1]);
    while(!q.empty())
    {
        p=q.front(); q.pop();
        if(abs(p.x-node[n].x)+abs(p.y-node[n].y)<=1000)
        return 1;
        for(int i=2; i<n; i++)
        if(vist[i]==0&&abs(p.x-node[i].x)+abs(p.y-node[i].y)<=1000)
        {
            vist[i]=1; q.push(node[i]);
        }
    }
    return 0;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        n+=2;
        for(int i=1; i<=n; i++)
        scanf("%d%d",&node[i].x,&node[i].y);
        int flog=bfs();
        printf("%s\n",flog?"happy":"sad");
    }
}