首页 > 代码库 > hdu 4771 bfs 从起点经过几个特定的点所需的最短时间
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\n",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\n"); 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 }
hdu 4771 bfs 从起点经过几个特定的点所需的最短时间
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。