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"); } }