nyoj 284 坦克大战（优先队列）

题目链接：http://acm.nyist.net/JudgeOnline/status.php?pid=284

特殊数据：

5 5

BBEEY

EEERB

SSERB

SSETB

非优先队列：

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<string>

 #include<cmath>

 #include<map>

 #include<queue>

 using namespace std;

 int e1,e2,m,n;

 int  mapp[][];

 int  vis[][];

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

 int ans;

 struct T

 {

     int x,y;

 }now,eed;

 int bfs(int s1,int s2)

 {

     queue< T >aa;

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

     now.x=s1;now.y=s2;

     aa.push(now);

     while(!aa.empty())

     {

         eed=aa.front();

            aa.pop();

           if(eed.x==e1 && eed.y==e2)

               {

               if(ans>vis[eed.x][eed.y])

                   ans=vis[eed.x][eed.y];

                }

         for(int i=;i<;i++)

         {

           now.x=eed.x+dir[i][];now.y=eed.y+dir[i][];

             //cout<<now.x<<" "<<now.y<<" "<<endl;

             if( mapp[now.x][now.y]!= )

             {

                 if(vis[now.x][now.y]==)

                     { vis[now.x][now.y]=mapp[now.x][now.y]+vis[eed.x][eed.y]; aa.push(now); }

                   else if(mapp[now.x][now.y]+vis[eed.x][eed.y]<vis[now.x][now.y])

                    {

                       vis[now.x][now.y]= mapp[now.x][now.y]+vis[eed.x][eed.y] ;

                       aa.push(now);

                    }

             }

         }

     }

     return ans;

 //5 5

 //BBEEY

 //EEERB

 //SSERB

 //SSERB

 //SSETB

 }

 int main()

 {

     int i,j,k,t,s1,s2;

     char s;

     while(cin>>m>>n && m+n)

     {ans=;

         memset(mapp,,sizeof(mapp));

         memset(vis,,sizeof(vis));

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

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

             {

               cin>>s;

               if(s=='Y')

                  {s1=i;s2=j;}

               else if(s=='T')

                {e1=i;e2=j; mapp[i][j]=;}

                 else if(s=='B')

                    mapp[i][j]=;

                   else if(s=='E')

                      mapp[i][j]=;

                       else mapp[i][j]=;

             }

             int mm=bfs(s1,s2);

             if(mm<)

                 cout<<ans<<endl;

               else cout<<-<<endl;

     }

     return ;

 }

优先队列：

 #include<queue>

 #include<algorithm>

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 using namespace std;

 char map[][];

 int  vis[][],m,n;

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

 int sx,sy,ex,ey;

 struct T

 {

     int x,y,step;

 }now,eed;

 bool operator<( T a, T b ){

     return a.step>b.step;

 }

 priority_queue<T>pp;

 bool judge(int x,int y)

 {

     if(x< || x>m || y< || y>n || vis[x][y]== || map[x][y]=='S' || map[x][y]=='R')

      return false;

      return true;

 }

 int bfs()

 {

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

     now.x = sx;  now.y = sy; now.step = ;

     vis[now.x][now.y]=;

     pp.push(now);

     while(!pp.empty())

     {

         eed = pp.top();

         pp.pop();

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

         if(eed.x == ex && eed.y==ey)

             return  eed.step;

         for(int i=;i<;i++)

         {

             now.x = eed.x+dir[i][];

             now.y = eed.y+dir[i][];

             if(judge(now.x ,now.y))

             {

                 if(map[now.x][now.y] == 'B')

                     now.step = eed.step+;

                     else

                         now.step = eed.step+;

                 vis[now.x][now.y]= ;

                 pp.push(now);

             }

         }

     }

     return -;

 }

 int main()

 {

     while(scanf("%d %d",&m,&n) && m+n)

     {

         memset(vis,,sizeof(vis));

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

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

         {

             scanf(" %c",&map[i][j]);

             if(map[i][j] == 'Y')

             {

                 sx = i;sy = j;

             }

             if(map[i][j] == 'T')

             {

                 ex = i;ey = j;

             }

         }

              int ans = bfs();

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

     }

     return ;

 }

巴特西

nyoj 284 坦克大战（优先队列）

最新文章

热门文章

巴特西

nyoj 284 坦克大战 （优先队列）

最新文章

热门文章

nyoj 284 坦克大战（优先队列）