首页 > 代码库 > poj3669 广搜
poj3669 广搜
//好久没刷题了，生疏了。
题意分析：
题意理解为在一个二维的正向坐标轴上，一个点（流星）连同它的上下左右的四个点会在某一个时刻被破坏。一个人在原点，问她到达安全区的最小时间是多少。
代码思路：
从原点开始搜索，如果当前的点是安全的（不会被破坏掉），那么就结束了。不然的话，向四个方向搜索，如果该方向的点没有被搜索过，并且到达该点的时间小于那一点被破坏的最小时间减一，那么就认为该点是可以到达的。记录到达该点的最小时间，把该点入队。
搜索的之前的处理是这样的。把每个点都设置为安全（永远不会被破坏），该点被破坏的时间为INF。读入数据的时候，对每一个输入，我们对五个点(输入坐标的点和其上下左右的四个点)进行处理：该点会被破坏，每次取该点被破坏的最小时间。
需要注意的是：虽然输入的坐标范围x,y是[0,300]，但是安全点的坐标可能大于300，最大可能是302。我就这样错了一次。
个人的代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<queue> 5 #include<algorithm> 6 using namespace std; 7 8 const int N = 305,INF=1010; 9 struct node10 {11 int x,y;12 bool f;//会不会被破坏13 int t;//被破坏最小时间14 int s;//走到这里需要的最小时间15 }p[N][N];16 bool vis[N][N];17 int step;18 bool isin(int x,int y)19 {20 return x<=N&&x>=0&&y<=N&&y>=0;21 }22 int dx[5]={0,0,0,1,-1};23 int dy[5]={0,1,-1,0,0};24 queue<node> q;25 node p1,p2;26 void bfs()27 {28 int i,j,k;29 while(!q.empty())30 {31 p1=q.front();32 q.pop();33 //printf("%d %d %d\n",p1.x,p1.y,p1.s);34 if(p1.f==0) {step=p1.s;break;}35 for(k=1;k<5;k++)36 {37 i=p1.x+dx[k];38 j=p1.y+dy[k];39 if(!vis[i][j]&&isin(i,j))40 {41 if(p1.s+1<p[i][j].t)42 {43 p[i][j].s=p1.s+1;44 q.push(p[i][j]);45 vis[i][j]=1;46 }47 }48 }49 }50 }51 int main()52 {53 //freopen("test.txt","r",stdin);54 int m,i,x,y,t,j;55 while(scanf("%d",&m)!=EOF)56 {57 for(i=0;i<N;i++){58 for(j=0;j<N;j++){59 p[i][j].x=i;60 p[i][j].y=j;61 p[i][j].f=0;62 p[i][j].t=INF;63 }64 }65 for(i=0;i<m;i++){66 scanf("%d%d%d",&x,&y,&t);67 for(j=0;j<5;j++)68 {69 int a=x+dx[j],b=y+dy[j];70 if(isin(a,b))71 {72 p[a][b].f=1;73 p[a][b].t=min(p[a][b].t,t);74 }75 }76 }77 while(!q.empty()) q.pop();78 p[0][0].s=0;79 q.push(p[0][0]);80 vis[0][0]=1;81 step=-1;82 memset(vis,0,sizeof(vis));83 bfs();84 printf("%d\n",step);85 }86 return 0;87 }
poj3669 广搜
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。