首页 > 代码库 > BZOJ 1611: [Usaco2008 Feb]Meteor Shower流星雨

BZOJ 1611: [Usaco2008 Feb]Meteor Shower流星雨

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1611

解:直接广搜。。。

程序:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
#define maxn 210000000
using namespace std;
int ans;
int f[500][500];
bool vis[500][500];
int h[5]={0,-1,1,0,0},l[5]={0,0,0,-1,1};
struct ding{
  int x,y,t;
};
queue<ding>q; 
bool check(int x,int y)
{
  if ((x<0)||(y<0)) return false;
  return true;
}
int main()
{
  int m;scanf("%d",&m);
  for (int i=0;i<=400;i++)
   for (int j=0;j<=400;j++)
   f[i][j]=maxn; 
  int x1,y1,t1;
  for (int i=1;i<=m;i++)
  {
    scanf("%d%d%d",&x1,&y1,&t1);
    for (int j=0;j<=4;j++)
    if (check(x1+h[j],y1+l[j])) f[x1+h[j]][y1+l[j]]=min(f[x1+h[j]][y1+l[j]],t1);
  }
  q.push((ding){0,0,0});
  vis[0][0]=true;
  while (!q.empty())
  {
      ding now=q.front();
      q.pop();
      if (f[now.x][now.y]==maxn) 
    {
      printf("%d\n",now.t);
      return 0; 
    }
    for (int i=1;i<=4;i++)
     if (check(now.x+h[i],now.y+l[i]))
      if (f[now.x+h[i]][now.y+l[i]]>now.t+1)
       if (!vis[now.x+h[i]][now.y+l[i]])
       {
            vis[now.x+h[i]][now.y+l[i]]=true;
         q.push((ding){now.x+h[i],now.y+l[i],now.t+1});
       }
  }
  printf("-1\n");
  return 0;
}

 

BZOJ 1611: [Usaco2008 Feb]Meteor Shower流星雨