CF1130C Connect

先说几句

难度适合。简单暴力。

解题思路

对于起始位置和终止位置，找出其分别所属的连通分量。

对这两个连通分量里的位置排序。如果相等，就说明起点和终点属于同一个连通分量。不需要挖隧道。直接输出 $0$$0$。

否则，就对这两个连通分量里的点进行一个 $O(n^2)$$O(n^2)$ 的双重循环暴力查找。

奉上代码

千万不要抄，小心棕名！

xxxxxxxxxx
// 1130C Connect
#include <bits/stdc++.h>
#define var long long
#define SIZE 55
using namespace std;

char a[SIZE][SIZE];
int n;
bool vis1[SIZE][SIZE]={0};
bool vis2[SIZE][SIZE]={0};
vector<pair<int, int>> b;
vector<pair<int, int>> c;

const int dx[]={-1, 1,  0, 0};
const int dy[]={ 0, 0, -1, 1};

void dfs1(int i, int j)
{
    if(i<0 || i>=n || j<0 || j>=n)
        return;
    if(vis1[i][j])
        return;
    if(a[i][j]=='1')
        return;
    vis1[i][j]=1;
    b.push_back({i, j});
    for(int k=0; k<4; k++)
    {
        int ni=i+dx[k];
        int nj=j+dy[k];
        dfs1(ni, nj);
    }
}

void dfs2(int i, int j)
{
    if(i<0 || i>=n || j<0 || j>=n)
        return;
    if(vis2[i][j])
        return;
    if(a[i][j]=='1')
        return;
    vis2[i][j]=1;
    c.push_back({i, j});
    for(int k=0; k<4; k++)
    {
        int ni=i+dx[k];
        int nj=j+dy[k];
        dfs2(ni, nj);
    }
}

inline int hamintonDistance(pair<int, int> a, pair<int, int> b)
{
    return (a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second);
}

int main()
{
    cin>>n;
    int si, sj; cin>>si>>sj; si--; sj--;
    int ei, ej; cin>>ei>>ej; ei--; ej--;
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            cin>>a[i][j];
            
    dfs1(si, sj);
    dfs2(ei, ej);
    
    sort(b.begin(), b.end());
    sort(c.begin(), c.end());
    
    /*
    for(auto x:b)
        cout<<x.first<<" "<<x.second<<endl;
    cout<<endl;
    for(auto x:c)
        cout<<x.first<<" "<<x.second<<endl;
    cout<<endl;
    */
    
    if(b==c)
    {
        cout<<0;
        return 0;
    }
    
    int Min=INT_MAX;    
    for(auto x:b)
        for(auto y:c)
        {
            int dist=hamintonDistance(x, y);
            if(dist<Min) Min=dist;
        }
    cout<<Min;

    return 0;
}