poj3669 广搜

//好久没刷题了，生疏了。

题意分析：

　　题意理解为在一个二维的正向坐标轴上，一个点（流星）连同它的上下左右的四个点会在某一个时刻被破坏。一个人在原点，问她到达安全区的最小时间是多少。

代码思路：　　

　　从原点开始搜索，如果当前的点是安全的（不会被破坏掉），那么就结束了。不然的话，向四个方向搜索，如果该方向的点没有被搜索过，并且到达该点的时间小于那一点被破坏的最小时间减一，那么就认为该点是可以到达的。记录到达该点的最小时间，把该点入队。

　　搜索的之前的处理是这样的。把每个点都设置为安全（永远不会被破坏），该点被破坏的时间为INF。读入数据的时候，对每一个输入，我们对五个点(输入坐标的点和其上下左右的四个点)进行处理：该点会被破坏，每次取该点被破坏的最小时间。

　　需要注意的是：虽然输入的坐标范围x,y是[0,300]，但是安全点的坐标可能大于300，最大可能是302。我就这样错了一次。

个人的代码：

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<queue>

 #include<algorithm>

 using namespace std;

 const int N = ,INF=;

 struct node

 {

     int x,y;

     bool f;//会不会被破坏

     int t;//被破坏最小时间

     int s;//走到这里需要的最小时间

 }p[N][N];

 bool vis[N][N];

 int step;

 bool isin(int x,int y)

 {

     return x<=N&&x>=&&y<=N&&y>=;

 }

 int dx[]={,,,,-};

 int dy[]={,,-,,};

 queue<node> q;

 node p1,p2;

 void bfs()

 {

     int i,j,k;

     while(!q.empty())

     {

         p1=q.front();

         q.pop();

         //printf("%d  %d  %d\n",p1.x,p1.y,p1.s);

         if(p1.f==) {step=p1.s;break;}

         for(k=;k<;k++)

         {

             i=p1.x+dx[k];

             j=p1.y+dy[k];

             if(!vis[i][j]&&isin(i,j))

             {

                 if(p1.s+<p[i][j].t)

                 {

                     p[i][j].s=p1.s+;

                     q.push(p[i][j]);

                     vis[i][j]=;

                 }

             }

         }

     }

 }

 int main()

 {

     //freopen("test.txt","r",stdin);

     int m,i,x,y,t,j;

     while(scanf("%d",&m)!=EOF)

     {

         for(i=;i<N;i++){

             for(j=;j<N;j++){

                 p[i][j].x=i;

                 p[i][j].y=j;

                 p[i][j].f=;

                 p[i][j].t=INF;

             }

         }

         for(i=;i<m;i++){

             scanf("%d%d%d",&x,&y,&t);

             for(j=;j<;j++)

             {

                 int a=x+dx[j],b=y+dy[j];

                 if(isin(a,b))

                 {

                     p[a][b].f=;

                     p[a][b].t=min(p[a][b].t,t);

                 }

             }

         }

         while(!q.empty()) q.pop();

         p[][].s=;

         q.push(p[][]);

         vis[][]=;

         step=-;

         memset(vis,,sizeof(vis));

         bfs();

         printf("%d\n",step);

     }

     return ;

 }

巴特西

poj3669 广搜

最新文章

热门文章