首页 > 代码库 > poj3026(Borg Maze)
poj3026(Borg Maze)
题目大意：
在银河系中有一强大生物个体Borg，每个个体之间都有一种联系。让我们帮忙写个程序扫描整个迷宫并同化隐藏在迷宫的相异个体的最小代价。
A 代表相异个体。空格代表什么没有，#代表障碍，S为开始点。扫描可以上下左右。
测试数据：
26 5##### #A#A### # A##S ####### 7 7##### #AAA#### A## S #### ##AAA########
解题思路：
简化题意就是从最少需要多少步将S和所有的A联系起来.第一组事例：S->A（1，1）两步+S->A（1，3）四步+A（1，3）->A（2，4）两步=8步。
这题的实质是最小生成树，然后实在搜索中实现最小生成树。因为是求最小的步数，所以用到广搜，我的思路是先将S的坐标进入BFS，将S到所有A的距离记录lowcost数组，然后从lowcost数组里找到最小的一个距离，然后记录其坐标，将其坐标进入到BFS，然后从该坐标搜索到其他A的距离更新lowcost，使其始终保存到各个A最小的距离。最后输出所有距离即可。实质是dijstra思想。
还有一点就是再输入m，n的时候可能有很多个空格，所以用一个getchar（）是不行的。需要用一个数组c将所有的空格gets（c）。出来。这样才能正确的建图。
代码：
1 #include <algorithm> 2 #include <iostream> 3 #include <sstream> 4 #include <cstdlib> 5 #include <cstring> 6 #include <cstdio> 7 #include <string> 8 #include <bitset> 9 #include <vector> 10 #include <queue> 11 #include <stack> 12 #include <cmath> 13 #include <list> 14 //#include <map> 15 #include <set> 16 using namespace std; 17 /***************************************/ 18 #define ll long long 19 #define int64 __int64 20 /***************************************/ 21 const int INF = 0x7f7f7f7f; 22 const double eps = 1e-8; 23 const double PIE=acos(-1.0); 24 const int d1x[]= {0,-1,0,1}; 25 const int d1y[]= {-1,0,1,0}; 26 const int d2x[]= {0,-1,0,1}; 27 const int d2y[]= {1,0,-1,0}; 28 const int fx[]= {-1,-1,-1,0,0,1,1,1}; 29 const int fy[]= {-1,0,1,-1,1,-1,0,1}; 30 /***************************************/ 31 void openfile() 32 { 33 freopen("data.in","rb",stdin); 34 freopen("data.out","wb",stdout); 35 } 36 /**********************华丽丽的分割线,以上为模板部分*****************/ 37 char map[100][100]; 38 int lowcost[100][100]; 39 int vis[100][100]; 40 int vis1[100][100]; 41 int cnt[100][100]; 42 int x[105],y[105]; 43 int d; 44 int sum; 45 int miin; 46 int m,n; 47 int ce1; 48 int cnt1; 49 int BFS(int x1,int y1) 50 { 51 int i,j; 52 queue<int >Q; 53 Q.push(x1); 54 Q.push(y1); 55 int v1,v2; 56 int sum1=0; 57 memset(vis,0,sizeof(vis)); 58 memset(cnt,0,sizeof(cnt)); 59 while(!Q.empty()) 60 { 61 v1=Q.front(); 62 Q.pop(); 63 v2=Q.front(); 64 Q.pop(); 65 if (vis[v1][v2]==-1) 66 continue; 67 if (map[v1][v2]==‘A‘&&!vis1[v1][v2]) 68 { 69 if (cnt[v1][v2]<lowcost[v1][v2]) 70 { 71 lowcost[v1][v2]=cnt[v1][v2]; 72 } 73 sum1++; 74 if (sum1==cnt1-d) 75 { 76 return 0; 77 } 78 } 79 vis[v1][v2]=-1; 80 if (v1>=0&&v1<n&&v2>=0&&v2<m) 81 { 82 if (v1-1>=0&&map[v1-1][v2]!=‘#‘&&vis[v1-1][v2]!=-1) 83 { 84 Q.push(v1-1); 85 Q.push(v2); 86 cnt[v1-1][v2]=cnt[v1][v2]+1; 87 } 88 if (v1+1<n&&map[v1+1][v2]!=‘#‘&&vis[v1+1][v2]!=-1) 89 { 90 Q.push(v1+1); 91 Q.push(v2); 92 cnt[v1+1][v2]=cnt[v1][v2]+1; 93 } 94 if (v2-1>=0&&map[v1][v2-1]!=‘#‘&&vis[v1][v2-1]!=-1) 95 { 96 Q.push(v1); 97 Q.push(v2-1); 98 cnt[v1][v2-1]=cnt[v1][v2]+1; 99 }100 if (v2+1<m&&map[v1][v2+1]!=‘#‘&&vis[v1][v2+1]!=-1)101 {102 Q.push(v1);103 Q.push(v2+1);104 cnt[v1][v2+1]=cnt[v1][v2]+1;105 }106 }107 }108 }109 int main()110 {111 int max;112 int cas;113 scanf("%d",&cas);114 while(cas--)115 {116 scanf("%d%d",&m,&n);117 char c[50];118 int i,j;119 cnt1=0;120 d=0;121 max=0;122 for(i=0; i<n; i++)123 for(j=0; j<m; j++)124 lowcost[i][j]=INF;125 for(i=0; i<n; i++)126 {127 gets(c);128 for(j=0; j<m; j++)129 {130 scanf("%c",&map[i][j]);131 if (map[i][j]==‘A‘||map[i][j]==‘S‘)132 {133 if (map[i][j]==‘S‘)134 {135 x[d]=i;136 y[d]=j;137 d++;138 }139 cnt1++;140 }141 }142 }143 memset(vis1,0,sizeof(vis1));144 for(ce1=0,j=0; j<d; j++)145 {146 BFS(x[j],y[j]);147 for(miin=INF,i=0; i<n; i++)148 for(int k=0; k<m; k++)149 {150 if (lowcost[i][k]<miin&&!vis1[i][k])151 {152 miin=lowcost[i][k];153 x[d]=i;154 y[d]=k;155 }156 }157 vis1[x[d]][y[d]]=1;158 d++;159 max+=miin;160 if (d==cnt1)161 break;162 }163 printf("%d\n",max);164 }165 return 0;166 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。