ACwing 4004.传送阵

原题链接: 4004. 传送阵 - AcWing题库https://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连通块的所有可能搭配
• 输出这些搭配的最小值

代码如下： 

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 60;
char g[N][N];
int n;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
bool st[N][N],st2[N][N];
void dfs1(int x,int y)//标记起点所在连通块的所有点
{
    st[x][y]=true;
    for(int i=0;i<4;i++)
    {
        int a=x+dx[i],b=y+dy[i];
        if(!st[a][b]&&g[a][b]=='0'&&a>0&&b>0&&a<=n&&b<=n) 
        {
            //printf("g[%%d][%%d]==%%c  ",a,b,g[a][b]);
            //printf("现在标记:%%d %%d
",a,b);
            dfs1(a,b);
        }
    }
}
void dfs2(int x,int y)//标记终点所在连通块的所有点
{
    st2[x][y]=true;
    for(int i=0;i<4;i++)
    {
        int a=x+dx[i],b=y+dy[i];
        if(!st2[a][b]&&g[a][b]=='0'&&a>0&&b>0&&a<=n&&b<=n) 
        {
            dfs2(a,b);
        }
    }
}
int main()
{
    cin>>n;
    int r1,c1,r2,c2;
    cin>>r1>>c1>>r2>>c2;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>g[i][j];
    
    dfs1(r1,c1);
    if(st[r2][c2]) cout<<0<<endl;//判断是否连通
    else
    {
        dfs2(r2,c2);
         /*for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(st[i][j]) cout<<1<<" ";
                else
                cout<<0<<" ";
            }
            cout<<endl;
        }
        */
        int res=0x3f3f3f3f;
        for(int i=1;i<=n;i++)//四重循环暴力枚举所有可能的组合
        {
            for(int j=1;j<=n;j++)
            {
                int x1=i,y1=j;
                if(!st[i][j]) continue;
                for(int k=1;k<=n;k++)
                {
                    for(int l=1;l<=n;l++)
                    {
                        if(!st2[k][l]) continue;
                        int x2=k,y2=l;
                        //cout<<x1<<" "<<y1<<" "<<x2<<" "<<y2<<endl;
                        res=min(res,(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
                        //在方格 (rs,cs) 和 (rt,ct) 处建立传送阵，所需成本为 (rs−rt)2+(cs−ct)2。
                    }
                }
 
            }
        }
        cout<<res<<endl;
    }
    return 0;
}
 

 

作者：机械之忍

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

来源：AcWing

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

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

我的QQ:2907065305