澳门新葡亰平台官网BFS——广搜的例子,以前做ACM的时候用的,现在拿出来看看

by admin on 2020年1月18日

#include <cstdlib>
#include <iostream>
#include <queue>

using namespace std;

typedef struct point
{
        int i;
        int j;
        int time;
}point;           

int map[8][8],mapt[8][8],visited[8][8];
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
int si,sj,di,dj,n,m;

void init()
{
     int i,j;
     memset(mapt,0,sizeof(mapt));
     memset(visited,0,sizeof(visited));
     for(i=0;i<n;i++)
     for(j=0;j<m;j++)
     {
         if(map[i][j]==2)
         {
             si=i;
             sj=j;
         }
         if(map[i][j]==3)
         {
             di=i;
             dj=j;
         }
     }
}

bool isbound(int x,int y)
{
     if(x>=0&&x<n&&y>=0&&y<m)
         return true;
     return false;
}   

bool bfs()
{
     int time=6,i,j;
     point cur,next;
     queue<point>Q;
     cur.i=si;
     cur.j=sj;
     cur.time=6;
     mapt[cur.i][cur.j]=0;
     visited[cur.i][cur.j]=1;
     Q.push(cur);
     while(!Q.empty())
     {
            cur=Q.front();
            Q.pop();         
           if(map[cur.i][cur.j]==3)
               return true;
           for(i=0;i<4;i++)
           {
               next.i=cur.i+dir[i][0];
               next.j=cur.j+dir[i][1];
               next.time=cur.time – 1;
               if(isbound(next.i,
next.j)&&map[next.i][next.j]!=0&&next.time>0&&!visited[next.i][next.j])
               {      
                        if(map[next.i][next.j]==4)
                        {
                             next.time=6;
                             visited[next.i][next.j]=1;
                        }
                       
mapt[next.i][next.j]=mapt[cur.i][cur.j]+1;
                        Q.push(next);
               }        
           }
     }
     return false;
}
          
int main(int argc,char *argv[])
{
    int numcase;
    cin>>numcase;
    while (numcase–)
    {
          int i, j;
          scanf(“%d%d”,&n,&m);
          for (i=0;i<n;i++)
          for (j=0;j<m;j++)
              scanf(“%d”,&map[i][j]);
          init ();   
          if (bfs())
             printf(“%dn”,mapt[di][dj]);
          else
             printf(“-1n”);  
    }
   // system(“PAUSE”);
    return EXIT_SUCCESS;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图