poj-3669

http://poj.org/problem?id=3669

广搜

#include<stdio.h>
#include<iostream>
#include<math.h>
#include<stdlib.h>
#include<ctype.h>
#include<algorithm>
#include<vector>
#include<string.h>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<sstream>
#include<time.h>
#include<utility>
#include<malloc.h>
#include<stdexcept>

using namespace std;

int n;

struct ss
{
    int x;
    int y;
    int tm;
}p[50010];

int pp[333][333];//最小被砸时间 初始无穷大
int vis[333][333];
int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};

bool cmp (ss a ,ss b)
{
    return a.tm < b.tm;
}

int bfs ()
{
    memset(vis,0,sizeof(vis));
    queue<ss> q ;
    ss qq ;
    ss qqq ;
    qq.x = 0;
    qq.y = 0;
    qq.tm = 0;
    q.push(qq);

    while (!q.empty())
    {
        qqq = q.front();
        q.pop();
        for(int i=0;i<4;i++)
        {
            qq = qqq;
            qq.x = qq.x + dir[i][0];
            qq.y = qq.y + dir[i][1];
            qq.tm = qq.tm+1;
            if(qq.x>=0 && qq.y>=0 && qq.tm < pp[qq.x][qq.y] && !vis[qq.x][qq.y] )
            {
                vis[qq.x][qq.y] = 1;
                if (pp[qq.x][qq.y] > p[n-1].tm)
                {
                    return qq.tm;
                }
                q.push(qq);
            }
        }
    }
    return -1;
}

int main ()
{
    while (scanf("%d",&n)!=EOF)
    {
        for(int i=0;i<=322;i++)
            for(int j=0;j<=322;j++)
            {
                pp[i][j] = 10000;
            }

        for(int i=0;i<n;i++)
        {
            scanf("%d %d %d",&p[i].x,&p[i].y,&p[i].tm );
        }
        //对陨石降落时间排序
        sort(p,p+n,cmp);

        for(int i=0;i<n;i++)
            for(int j=0;j<4;j++)
            {
                if (pp[p[i].x][p[i].y] > p[i].tm)
                    pp[p[i].x][p[i].y] = p[i].tm;

                int xx = p[i].x + dir[j][0];
                int yy = p[i].y + dir[j][1];

                if (xx >= 0 && yy >= 0 && pp[xx][yy] > p[i].tm)
                {
                    pp[xx][yy] = p[i].tm;
                }
            }


        if(pp[0][0] == 0)
        {
            printf("-1\n");
        }
        else
        {
            printf("%d\n",bfs());
        }
    }
    return 0;
}