蓝桥集训之奶牛选美

蓝桥集训之奶牛选美

• 核心思想：Flood fill(dfs)

  • 用Flood fill将两个连通块搜出 保存
  • 然后分别遍历两个连通块 算两点间距离

•   #include<iostream>
    #include<cstring>
    #include<vector>
    
    using namespace std;
    const int N = 55;
    typedef pair<int,int> PII;
    
    int dx[4] = {0,-1,0,1} , dy[4] = {1,0,-1,0};
    vector<PII> points[2];  //存两个连通块
    char g[N][N];
    int n,m;
    
    void dfs(int x,int y,vector<PII> &ps)
    {
        g[x][y] = '.';  //找到X 改为. 不影响后续递归
        ps.push_back({x,y});  //将X的点存入
        
        for(int i=0;i<4;i++)
        {
            int a = x + dx[i] , b = y + dy[i];
            if (a >= 0 && a < n && b >= 0 && b < m && g[a][b] == 'X')
                dfs(a,b,ps);  //找到附近的X 继续搜
        }
    }
    int main()
    {
        cin>>n>>m;
        for(int i=0;i<n;i++) cin>>g[i];
        
        for(int i=0,k=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                //找到一个时 dfs搜出一整个连通块 下次再找到 找出第二个
                if(g[i][j] == 'X') dfs(i,j,points[k++]);  
            }
        }
        
        int res = 1e8;
        for(auto a : points[0])
            for(auto b : points[1])
                res = min(res , abs(a.first - b.first) + abs(a.second - b.second) - 1);
                
        cout<<res<<endl;
        return 0;
    }