首页 > 代码库 > POJ 3669

POJ 3669

2024-08-01 19:01:15   219人阅读

题意：已知流星的颗数，落地的坐标和落地时间，若流星落在某点则该点周围的四点也会被波及，现在要求你到达一点没有被流星击过的点最少时间

注意：只能在第一象限内包括X，Y轴的正半轴

 

 1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4 #include <cctype> 5 #include <cmath> 6 #include <time.h> 7 #include <string> 8 #include <map> 9 #include <stack>10 #include <set>11 #include <queue>12 #include <vector>13 #include <algorithm>14 #include <iostream>15 using namespace std;16 typedef long long ll;17 typedef pair<int,int> P;18 #define PI acos( -1.0 )19 const double E = 1e-8;20 const int INF = 0x7fffffff;21 22 const int NO = 300 + 5;23 int m[NO][NO];24 int step[NO][NO];25 int mark[NO][NO];26 int dir[][2] = { {-1,0}, {1,0}, {0,-1}, {0,1} };27 int n;28 29 void init()30 {31     for( int i = 0; i < NO; ++i )32         for( int j = 0; j < NO; ++j )33             m[i][j] = INF;34 }35 36 void init1( int x, int y, int c )37 {38     for( int i = 0; i < 4; ++i )39     {40         int xx = x + dir[i][0];41         int yy = y + dir[i][1];42         if( xx >= 0 && yy >= 0 )43             m[xx][yy] = min( m[xx][yy], c );44     }45 }46 47 void bfs()48 {49     queue <P> q;50     q.push( P( 0, 0 ) );51     mark[0][0] = 0;52     memset( step, 0, sizeof( step ) );53     while( !q.empty() )54     {55         P t = q.front(); q.pop();56         int x = t.first;57         int y = t.second;58         mark[x][y] = 0;59         if( m[x][y] == INF )60         {61             printf( "%d\n", step[x][y] );62             return;63         }64         for( int i = 0; i < 4; ++i )65         {66             int dx = x + dir[i][0];67             int dy = y + dir[i][1];68             if( dx >= 0 && dy >= 0 && ( m[dx][dy] == INF || m[dx][dy] > step[x][y]+1 ) && !mark[dx][dy] )69             {70                 mark[dx][dy] = 1;71                 step[dx][dy] = step[x][y] + 1;72                 q.push( P( dx, dy ) );73             }74         }75     }76     puts( "-1" );77 }78 79 int main()80 {81     scanf( "%d", &n );82     int a, b, c;83     init();84     for( int i = 0; i < n; ++i )85     {86         scanf( "%d%d%d", &a, &b, &c );87         m[a][b] = min( m[a][b], c );88         init1( a, b, c );89     }90     bfs();91     return 0;92 }
View Code

 

POJ 3669


联系
我们