首页 > 代码库 > hdu 4771 Stealing Harry Potter's Precious （2013亚洲区杭州现场赛）（搜索 bfs + dfs） 带权值的路径
hdu 4771 Stealing Harry Potter's Precious （2013亚洲区杭州现场赛）（搜索 bfs + dfs） 带权值的路径
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4771
题目意思：‘@‘ 表示的是起点，‘#‘ 表示的是障碍物不能通过，‘.‘ 表示的是路能通过的；
目的：让你从 ‘@‘ 点出发，然后每个点只能走一次，求出最小的距离；
解题思路：先用 bfs 求解出任意两点之间的距离，用 ans[i][j],表示点 i 到点 j 的距离；
然后用 dfs 递归求出从起点经过所有点的距离中，比较出最小的；
AC代码：
1 #include<iostream> 2 #include<algorithm> 3 #include<cstdio> 4 #include<cstring> 5 #include<queue> 6 #include<string> 7 #include<cmath> 8 using namespace std; 9 int dir[4][2]={0,1,0,-1,1,0,-1,0}; 10 int m,n; 11 int sx,sy,T; 12 int ans[6][6];//点之间的距离 13 char Map[110][110]; 14 int vis[110][110];//标记路径 15 struct node 16 { 17 int x,y,step; 18 }a[6],now,eed; 19 int bfs(int T1,int ee,int vv) 20 { 21 int TT=0; 22 vis[a[T1].x][a[T1].y]=vv;//每次标记的都发生了变化，这样vis数组不用每次都清零 23 queue< node >p; 24 now.x = a[T1].x; 25 now.y = a[T1].y; 26 now.step = 0; 27 p.push(now); 28 while(!p.empty()) 29 { 30 now=p.front(); 31 p.pop(); 32 for(int i=T1+1; i<=T; i++) 33 { 34 if(now.x == a[i].x && now.y == a[i].y) 35 { 36 ans[T1][i]=ans[i][T1] = now.step; 37 TT++; 38 } 39 } 40 for(int i=0; i<4; i++) 41 { 42 eed.x = now.x + dir[i][0]; eed.y = now.y + dir[i][1]; 43 if(eed.x>=1 && eed.x<=m && eed.y>=1 && eed.y<=n && vis[eed.x][eed.y]!=vv && Map[eed.x][eed.y]!=‘#‘) 44 { 45 eed.step = now.step+1; 46 vis[eed.x][eed.y] = vv; 47 p.push(eed); 48 } 49 } 50 if(TT == ee) //如果该访问的点都访问了，直接返回； 51 return 1; 52 } 53 return -1 ;//如果其中有点不能访问到，直接返回-1，输出 -1 ； 54 } 55 56 int net[10],ans1; 57 void dfs(int x,int step,int sum) 58 { 59 if(step==T) 60 { 61 if(ans1>sum) ans1=sum; 62 return; 63 } 64 for(int i=0;i<=T;i++) 65 if(!net[i]) 66 { 67 net[i]=1; 68 dfs(i,step+1,sum+ans[x][i]); 69 net[i]=0; 70 } 71 } 72 int main() 73 { 74 int x,y; 75 // freopen("in1.txt","r",stdin); 76 // freopen("out1.txt","w",stdout); 77 while(cin>>m>>n && m+n) 78 { 79 ans1=1000000; 80 memset(ans,0,sizeof(ans)); 81 memset(net,0,sizeof(net)); 82 memset(vis,0,sizeof(vis)); 83 for(int i=1; i<=m; i++) 84 for(int j=1; j<=n; j++) 85 { 86 scanf(" %c",&Map[i][j]); 87 if(Map[i][j] == ‘@‘) 88 { 89 sx= i; sy = j; 90 } 91 } 92 scanf("%d",&T); 93 a[0].x=sx; a[0].y=sy; 94 for(int i=1; i<=T; i++) 95 { 96 scanf("%d %d",&x,&y); 97 a[i].x = x; 98 a[i].y = y; 99 }100 int flag = 0 ;101 for(int i = 0; i<T; i++)102 {103 104 flag = bfs(i,T-i,i+1);105 if(flag == -1)106 break;107 }108 if(flag == -1)109 printf("-1\n");110 else111 {112 net[0]=1;113 dfs(0,0,0);114 printf("%d\n",ans1);115 }116 }117 return 0;118 }
hdu 4771 Stealing Harry Potter's Precious （2013亚洲区杭州现场赛）（搜索 bfs + dfs） 带权值的路径
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。