[kuangbin带你飞]专题六 最小生成树 J - Borg Maze

布满荆棘的人生 2023-08-17 15:41 214阅读 0赞

J - Borg Maze

题目链接:https://vjudge.net/contest/66965#problem/J

题目:

博格是一个非常强大的种族,它来自银河系的三角洲象限。博格集体是用来描述博格文明群体意识的术语。每个博格人都通过复杂的子空间网络与集体联系,确保每个成员得到持续的监督和指导。

  1. 你的任务是帮助博格(是的,真的)通过开发一个程序,帮助博格估计扫描迷宫的最低成本,以便同化隐藏在迷宫中的外星人,在北部,西部,东部和南部移动脚步。棘手的是,搜索的开始是由100多个人组成的。每当外星人被同化时,或者在搜索开始时,该群体可能会分成两组或更多组(但他们的意识仍然是集体的)。搜索迷宫的成本被定义为搜索中涉及的所有组所覆盖的总距离。也就是说,如果原始组走五步,则分成两组,每组步行三步,总距离为11 = 5 + 3 + 3

输入
在输入的第一行有一个整数,N <= 50,给出输入中的测试用例数。每个测试用例以包含两个整数x,y的行开始,使得1 <= x,y <= 50.然后,跟随y行,每行x个字符。对于每个角色,空格“`”代表开放空间,哈希标记“#”代表障碍墙,大写字母“A”代表外星人,大写字母“S”代表’’代表搜索的开始。迷宫的周长总是关闭的,即没有办法从“S”的坐标中走出来。迷宫中至多有100个外星人,每个人都可以到达。
产量
对于每个测试用例,输出一行包含成功搜索迷宫的最小成本,不留外来人。
样本输入

  1. 2
  2. 6 5
  3. \#\#\#\#\#
  4. AA \#\#
  5. 一个#
  6. \#S \#\#
  7. \#\#\#\#\#
  8. 7 7
  9. \#\#\#\#\#
  10. \#AAA \#\#\#
  11. 一个#
  12. S \#\#\#
  13. \#\#
  14. \#AAA \#\#\#
  15. \#\#\#\#\#

样本输出

  1. 8
  2. 11

思路:这题一开始没看懂啥意思,百度了看的,先bfs求出每个A到S的距离,然后用最小生成树求出最小边权和即可

  1. //
  2. // Created by hanyu on 2019/8/1.
  3. //
  4. #include <algorithm>
  5. #include <iostream>
  6. #include <cstdio>
  7. #include <cstring>
  8. #include <queue>
  9. #include <set>
  10. #include<math.h>
  11. using namespace std;
  12. typedef long long ll;
  13. const int maxn=2e6+7;
  14. int father[maxn];
  15. int book[600][600],point[600][600];
  16. char str[600][600];
  17. int dir[4][2]={
  18. {-1,0},{
  19. 0,1},{
  20. 1,0},{
  21. 0,-1}};
  22. struct Point{
  23. int x,y,step;
  24. };
  25. struct Node{
  26. int u,v,w;
  27. bool operator<(const Node &other)const{
  28. return this->w<other.w;
  29. }
  30. }node[maxn];
  31. int find(int x)
  32. {
  33. if(x==father[x])
  34. return x;
  35. return father[x]=find(father[x]);
  36. }
  37. int n,m,num,cnt;
  38. void bfs(int sx,int sy)
  39. {
  40. memset(book,0,sizeof(book));
  41. Point now,next;
  42. queue<Point>qu;
  43. now.x=sx;
  44. now.y=sy;
  45. now.step=0;
  46. book[sx][sy]=1;
  47. qu.push(now);
  48. while(!qu.empty())
  49. {
  50. now=qu.front();
  51. qu.pop();
  52. for(int i=0;i<4;i++)
  53. {
  54. next.x=now.x+dir[i][0];
  55. next.y=now.y+dir[i][1];
  56. next.step=now.step+1;
  57. if(next.x>=0&&next.x<n&&next.y>=0&&next.y<m&&str[next.x][next.y]!='#'&&!book[next.x][next.y])
  58. {
  59. book[next.x][next.y]=1;
  60. qu.push(next);
  61. if(str[next.x][next.y]=='S'||str[next.x][next.y]=='A')
  62. {
  63. node[num].u=point[sx][sy];
  64. node[num].v=point[next.x][next.y];
  65. node[num++].w=next.step;
  66. }
  67. }
  68. }
  69. }
  70. }
  71. int kru(int n)
  72. {
  73. int res=0;
  74. for(int i=0;i<cnt;i++)
  75. father[i]=i;
  76. for(int i=0;i<n;i++)
  77. {
  78. int uu=find(node[i].u);
  79. int vv=find(node[i].v);
  80. if(uu==vv)
  81. continue;
  82. else
  83. {
  84. father[uu]=vv;
  85. res+=node[i].w;
  86. }
  87. }
  88. return res;
  89. }
  90. int main()
  91. {
  92. int T;
  93. scanf("%d",&T);
  94. char str1[maxn];
  95. while(T--)
  96. {
  97. scanf("%d%d",&m,&n);
  98. gets(str1);
  99. cnt=0;
  100. num=0;
  101. memset(point,0,sizeof(point));
  102. for(int i=0;i<n;i++)
  103. {
  104. gets(str[i]);
  105. for(int j=0;j<m;j++)
  106. {
  107. if(str[i][j]=='S'||str[i][j]=='A')
  108. point[i][j]=cnt++;
  109. }
  110. }
  111. for(int i=0;i<n;i++) {
  112. for (int j = 0; j < m; j++) {
  113. if(str[i][j]=='A'||str[i][j]=='S')
  114. bfs(i,j);
  115. }
  116. }
  117. sort(node,node+num);
  118. printf("%d\n",kru(num));
  119. }
  120. return 0;
  121. }

转载于:https://www.cnblogs.com/Vampire6/p/11285802.html

发表评论

表情:
评论列表 (有 0 条评论,214人围观)

还没有评论,来说两句吧...

相关阅读