hdu 4771 bfs 从起点经过几个特定的点所需的最短时间

【题意】：给你一个n*m的地图，问你从起点出发，必须经过几个特定的点所需的最短时间

【思路】：地图较小且这里最多有4个点必须经过的点，所以直接BFS就可以了，step[x][y][zt] 表示在点[x,y]且已经走过的点的状态为zt（二进制表示）（要是数据量大一点可以先预处理这些必须经过的点两两之间的最短距离再状态压缩dp）（直接看记录盼盼的代码算了）

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<queue>
  4 #include<cstring>
  5 using namespace std;
  6 struct node
  7 {
  8     int x,y;
  9     int zt,step;
 10 };
 11 bool vist[105][105][(1<<4)];
 12 int n,m,k,fx[4][2]={1,0,-1,0,0,1,0,-1},tol,qx,qy;
 13 char s[105][105];
 14 void bfs(int zt)
 15 {
 16     node p;
 17     p.x=qx;
 18     p.y=qy;
 19     p.step=0;
 20     p.zt=zt;
 21     memset(vist,false,sizeof(vist));
 22     vist[p.x][p.y][p.zt]=true;
 23     queue<node>q;
 24     q.push(p);
 25     while(!q.empty())
 26     {
 27         p=q.front();
 28         q.pop();
 29         if(p.zt==(1<<k)-1)
 30         {
 31             printf("%d
",p.step);
 32             return;
 33         }
 34         for(int i=0;i<4;i++)
 35         {
 36             node p1;
 37             p1.x=p.x+fx[i][0];
 38             p1.y=p.y+fx[i][1];
 39             p1.step=p.step+1;
 40             p1.zt=p.zt;
 41             if(p1.x>=0&&p1.x<n&&p1.y>=0&&p1.y<m&&s[p1.x][p1.y]!='#')
 42             {
 43                 if(s[p1.x][p1.y]>=1&&s[p1.x][p1.y]<=k)
 44                 {
 45                     int tmp=(1<<(s[p1.x][p1.y]-1));
 46                     p1.zt|=tmp;
 47                     if(!vist[p1.x][p1.y][p1.zt])
 48                     {
 49                         vist[p1.x][p1.y][p1.zt]=true;
 50                         q.push(p1);
 51                     }
 52                 }
 53                 else
 54                 {
 55                     if(!vist[p1.x][p1.y][p1.zt])
 56                     {
 57                         vist[p1.x][p1.y][p1.zt]=true;
 58                         q.push(p1);
 59                     }
 60                 }
 61             }
 62         }
 63     }
 64     printf("-1
");
 65 }
 66 int main()
 67 {
 68     while(scanf("%d%d",&n,&m)>0)
 69     {
 70         if(n==0&&m==0) break;
 71         tol=1;
 72         for(int i=0;i<n;i++)
 73         {
 74             scanf("%s",s[i]);
 75             for(int j=0;j<m;j++)
 76             {
 77                 if(s[i][j]=='@')
 78                 {
 79                     s[i][j]='.';
 80                     qx=i;
 81                     qy=j;
 82                 }
 83             }
 84         }
 85         scanf("%d",&k);
 86         int zt=0;
 87         for(int i=0;i<k;i++)
 88         {
 89             int x,y;
 90             scanf("%d%d",&x,&y);
 91             x--;
 92             y--;
 93             s[x][y]=tol++;
 94             if(x==qx&&y==qy)
 95             {
 96                 zt|=(1<<(s[x][y]-1));
 97             }
 98         }
 99         bfs(zt);
100     }
101     return 0;
102 }