首页 > 代码库 > POJ - 3669 Meteor Shower(bfs)
POJ - 3669 Meteor Shower(bfs)
题意:某人在时刻0从原点出发,在第一象限范围内移动。已知每个炸弹爆炸的地点和时刻,炸弹爆炸可毁坏该点和它上下左右的点。不能经过已毁坏的点,也不能在某点毁坏的时候位于该点。不会被炸弹毁坏的地方是安全之处,问某人到达安全之处的最短时间。
分析:bfs即可。注意:1、某点多次爆炸或受爆炸点影响而毁坏,取最早时间为该点的毁坏时间。2、bfs走过的点不能再走,注意标记。
#pragma comment(linker, "/STACK:102400000, 102400000")#include<cstdio>#include<cstring>#include<cstdlib>#include<cctype>#include<cmath>#include<iostream>#include<sstream>#include<iterator>#include<algorithm>#include<string>#include<vector>#include<set>#include<map>#include<stack>#include<deque>#include<queue>#include<list>#define Min(a, b) ((a < b) ? a : b)#define Max(a, b) ((a < b) ? b : a)const double eps = 1e-8;inline int dcmp(double a, double b){ if(fabs(a - b) < eps) return 0; return a > b ? 1 : -1;}typedef long long LL;typedef unsigned long long ULL;const int INT_INF = 0x3f3f3f3f;const int INT_M_INF = 0x7f7f7f7f;const LL LL_INF = 0x3f3f3f3f3f3f3f3f;const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f;const int dr[] = {0, -1, 0, 1, -1, -1, 1, 1};const int dc[] = {-1, 0, 1, 0, -1, 1, -1, 1};const int MOD = 1e9 + 7;const double pi = acos(-1.0);const int MAXN = 300 + 10;const int MAXT = 10000 + 10;using namespace std;int vis[MAXN][MAXN];int a[MAXN][MAXN];bool judge(int x, int y){ return x >= 0 && y >= 0;}int bfs(int sx, int sy){ queue<int> x, y, step; x.push(sx); y.push(sy); step.push(0); a[sx][sy] = 1; while(!x.empty()){ int tmpx = x.front(); x.pop(); int tmpy = y.front(); y.pop(); int tmpstep = step.front(); step.pop(); if(vis[tmpx][tmpy] == INT_INF) return tmpstep; for(int i = 0; i < 4; ++i){ int tx = tmpx + dr[i]; int ty = tmpy + dc[i]; if(judge(tx, ty)){ if(vis[tx][ty] == INT_INF) return tmpstep + 1; if(a[tx][ty]) continue; if(vis[tx][ty] > tmpstep + 1){ x.push(tx); y.push(ty); step.push(tmpstep + 1); a[tx][ty] = 1; } } } } return -1;}int main(){ int M; scanf("%d", &M); memset(vis, INT_INF, sizeof vis); while(M--){ int x, y, t; scanf("%d%d%d", &x, &y, &t); vis[x][y] = Min(vis[x][y], t); for(int i = 0; i < 4; ++i){ int tmpx = x + dr[i]; int tmpy = y + dc[i]; if(judge(tmpx, tmpy)) vis[tmpx][tmpy] = Min(vis[tmpx][tmpy], t); } } int ans = bfs(0, 0); printf("%d\n", ans); return 0;}
POJ - 3669 Meteor Shower(bfs)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。