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 
#include 
#include 
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 %dn",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< 
 
 
作者：机械之忍
 
链接：https://www.acwing.com/activity/content/code/content/1977734/
 
来源：AcWing
 
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 
 
本人刚开始写题解不久，很多地方还不成熟，为了让读者更好的理解思路和细节，我做这道题时的调试代码片段也保留了，我觉得这样能更直观的表达我的想法，如果各位有疑问之处，或者我写的哪里有错误，欢迎私信我或者在下方留言
 
我的QQ:2907065305