本文共 1894 字，大约阅读时间需要 6 分钟。
http://poj.org/problem?id=3669
注意理解题意：有m颗行星将会落在方格中（第一象限），第i颗行星在ti时间会摧毁（xi，yi）这个点和四周相邻的点，一个人开始在原点，然后只能在第一象限内行走，每单位时间移动一格，只能移动到当前未摧毁的点，问多少时间能到达安全地方。
开始题意理解错了，没有明白每一颗行星最多摧毁5个点，我们可以预处理出被行星摧毁的点，然后用bfs搜索。
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 //#include 15 #include 16 17 #define CL(arr, val) memset(arr, val, sizeof(arr))18 19 #define ll long long20 #define inf 0x7f7f7f7f21 #define lc l,m,rt<<122 #define rc m + 1,r,rt<<1|123 #define pi acos(-1.0)24 25 #define L(x) (x) << 126 #define R(x) (x) << 1 | 127 #define MID(l, r) (l + r) >> 128 #define Min(x, y) (x) < (y) ? (x) : (y)29 #define Max(x, y) (x) < (y) ? (y) : (x)30 #define E(x) (1 << (x))31 #define iabs(x) (x) < 0 ? -(x) : (x)32 #define OUT(x) printf("%I64d\n", x)33 #define lowbit(x) (x)&(-x)34 #define Read() freopen("a.txt", "r", stdin)35 #define Write() freopen("dout.txt", "w", stdout);36 #define maxn 100000000037 #define N 101038 using namespace std;39 40 int dir[5][2]={-1,0,1,0,0,1,0,-1,0,0};41 int vis[500][500];42 struct node43 {44 int x,y,time;45 };46 47 int bfs()48 {49 if(vis[0][0]==-1) return 0;50 node p;51 p.x=p.y=p.time=0;52 queue que;53 que.push(p);54 while(que.size())55 {56 node q=que.front();57 que.pop();58 for(int i=0;i<4;i++)59 {60 p=q;61 p.x=q.x+dir[i][0];62 p.y=q.y+dir[i][1];63 p.time++;64 if(p.x<0||p.y<0) continue; //出界了65 if(vis[p.x][p.y]==-1) return p.time; //到达安全地方66 if(p.time =0&&yy>=0) //预处理所有被摧毁的点，并赋值为被摧毁的最小时间。89 {90 if(vis[xx][yy]==-1) vis[xx][yy]=t;91 else vis[xx][yy]=min(t,vis[xx][yy]);92 }93 }94 }95 if(vis[0][0]==0) printf("-1\n");96 else printf("%d\n",bfs());97 return 0;98 }
转载于:https://www.cnblogs.com/nowandforever/p/4380036.html
