首页 > 代码库 > poj-3669-Meteor Shower-bfs
poj-3669-Meteor Shower-bfs
题意: 把地面看做第一象限的网格,有场流星雨,会下M颗流星,流星落到地面某一格会摧毁那一格和上下左右四格,这些地方之后都不能再走。现在Bessie 从[0,0]格出发,给你每一颗流星落到地面的坐标(整点)和时间,问Bessie最少用多少时间才能走到永远安全的点上,如果走不到输出-1。
思路:读入点和时间,然后在[301, 301]的网格上预处理,存入该点最先被摧毁的时间,然后在bfs的时候比较。永远不能到达标记为INT_MAX。
AC代码:
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <vector> 5 #include <queue> 6 #include <cstring> 7 #include <climits> 8 using namespace std; 9 10 int m;11 int const maxn = 302;12 int const mde = 50004;13 struct node14 {15 int x, y, t;16 bool operator < (const node that) const {17 return t < that.t;18 }19 node() {x = y = t = 0;}20 };21 int mp[maxn][maxn];22 int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};23 bool border(int x, int y)24 {25 if(x < 0 || y < 0 || y > 301 || x > 301) return false;26 return true;27 }28 void init()29 {30 for(int i = 0; i < maxn; i++) {31 for(int j = 0; j < maxn; j++) mp[i][j] = INT_MAX;32 }33 for(int i = 0; i < m; i++) {34 int a, b, c; scanf("%d%d%d", &a, &b, &c);35 if(c < mp[a][b]) mp[a][b] = c;36 for(int j = 0; j < 4; j++) {37 int dx = a + dir[j][0], dy = b + dir[j][1];38 if(border(dx, dy) && c < mp[dx][dy]) mp[dx][dy] = c;39 }40 }41 }42 void bfs(int &ans)43 {44 queue<node> q; node rec;45 q.push(rec);46 if(mp[0][0] == 0) return;47 bool inq[maxn][maxn]; memset(inq, 0, sizeof(inq)); inq[0][0] = 1;48 while(!q.empty()) {49 rec = q.front(); q.pop();50 if(mp[rec.x][rec.y] == INT_MAX) {ans = rec.t; return; }51 for(int i = 0; i < 4; i++) {52 node dn; dn.x = rec.x + dir[i][0]; dn.y = rec.y + dir[i][1]; dn.t = rec.t + 1;53 if(border(dn.x, dn.y) && mp[dn.x][dn.y] > dn.t && !inq[dn.x][dn.y]) {54 q.push(dn);55 inq[dn.x][dn.y] = 1;56 }57 }58 }59 }60 void work()61 {62 int ans = -1;63 init();64 bfs(ans);65 printf("%d\n", ans);66 }67 int main()68 {69 while(scanf("%d", &m) != EOF) work();70 return 0;71 }
poj-3669-Meteor Shower-bfs
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。