WHCSRL 技术网

ACwing 4004.传送阵

原题链接: 4004. 传送阵 - AcWing题库icon-default.png?t=L9C2https://www.acwing.com/problem/content/4007/

思路:

如果起点和终点是连通的,就无需建立传送门,直接输出0,否则起点和终点一定不连通,这也就意味着起点和中点位于两个独立的连通块中

那首先我们先想想这道题的暴力做法:不妨设起点位于A连通块中,终点位于B连通块中。只需依次枚举A连通块中的每个点(含起点)到B连通块中每个点(含终点)的所有可能距离,然后在这些距离中选择最小的输出即可。

到此,暴力的思路完毕,我们来分析一下暴力的时间复杂度:不妨设A连通块的点的数量为ma,B连通块的点的数量为mb,依据暴力做法,A中的每个点都要和B的所有点匹配,得出一个可能的距离,所以暴力的时间复杂度为O(ma*mb),当数据接近所给出的极限时,我们可以认为是O(n²*n²),按照题目所给的数据范围,50的四次方6250000<10的8次方,c++1s之内可以算出来,于是发现暴力做法可行

所以接下来做法很明确了:

  • 判断起点和终点是否连通
  • 标记起点所在连通块的所有点
  • 标记终点所在连通块的所有点
  • 暴力枚举A连通块和B连通块的所有可能搭配
  • 输出这些搭配的最小值

代码如下: 

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  4. using namespace std;
  5. const int N = 60;
  6. char g[N][N];
  7. int n;
  8. int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
  9. bool st[N][N],st2[N][N];
  10. void dfs1(int x,int y)//标记起点所在连通块的所有点
  11. {
  12. st[x][y]=true;
  13. for(int i=0;i<4;i++)
  14. {
  15. int a=x+dx[i],b=y+dy[i];
  16. if(!st[a][b]&&g[a][b]=='0'&&a>0&&b>0&&a<=n&&b<=n)
  17. {
  18. //printf("g[%%d][%%d]==%%c ",a,b,g[a][b]);
  19. //printf("现在标记:%%d %%d ",a,b);
  20. dfs1(a,b);
  21. }
  22. }
  23. }
  24. void dfs2(int x,int y)//标记终点所在连通块的所有点
  25. {
  26. st2[x][y]=true;
  27. for(int i=0;i<4;i++)
  28. {
  29. int a=x+dx[i],b=y+dy[i];
  30. if(!st2[a][b]&&g[a][b]=='0'&&a>0&&b>0&&a<=n&&b<=n)
  31. {
  32. dfs2(a,b);
  33. }
  34. }
  35. }
  36. int main()
  37. {
  38. cin>>n;
  39. int r1,c1,r2,c2;
  40. cin>>r1>>c1>>r2>>c2;
  41. for(int i=1;i<=n;i++)
  42. for(int j=1;j<=n;j++)
  43. cin>>g[i][j];
  44. dfs1(r1,c1);
  45. if(st[r2][c2]) cout<<0<<endl;//判断是否连通
  46. else
  47. {
  48. dfs2(r2,c2);
  49. /*for(int i=1;i<=n;i++)
  50. {
  51. for(int j=1;j<=n;j++)
  52. {
  53. if(st[i][j]) cout<<1<<" ";
  54. else
  55. cout<<0<<" ";
  56. }
  57. cout<<endl;
  58. }
  59. */
  60. int res=0x3f3f3f3f;
  61. for(int i=1;i<=n;i++)//四重循环暴力枚举所有可能的组合
  62. {
  63. for(int j=1;j<=n;j++)
  64. {
  65. int x1=i,y1=j;
  66. if(!st[i][j]) continue;
  67. for(int k=1;k<=n;k++)
  68. {
  69. for(int l=1;l<=n;l++)
  70. {
  71. if(!st2[k][l]) continue;
  72. int x2=k,y2=l;
  73. //cout<<x1<<" "<<y1<<" "<<x2<<" "<<y2<<endl;
  74. res=min(res,(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
  75. //在方格 (rs,cs) 和 (rt,ct) 处建立传送阵,所需成本为 (rs−rt)2+(cs−ct)2。
  76. }
  77. }
  78. }
  79. }
  80. cout<<res<<endl;
  81. }
  82. return 0;
  83. }

 

作者:机械之忍

链接:https://www.acwing.com/activity/content/code/content/1977734/

来源:AcWing

著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

本人刚开始写题解不久,很多地方还不成熟,为了让读者更好的理解思路和细节,我做这道题时的调试代码片段也保留了,我觉得这样能更直观的表达我的想法,如果各位有疑问之处,或者我写的哪里有错误,欢迎私信我或者在下方留言

我的QQ:2907065305