奶牛选美_牛客博客

思路

首先，发现题目的数据范围是1≤N,M≤50，很小， $5 0^{2} = 2500$ ,是三次方级别，如果把两个断点都枚举一遍，大概是 $1 0^{6}$ 级别，不会超时。

把题目意思抽象出来大致意思是：

给定两个顶点集合，在两个集合中各找一个点，求两个点之间的最短距离（这里的路线是只能横着走或者竖着走）

接下来给出一个性质

假设距离最短的路线的两个端点分别是 $(x_{1}, y_{1})$ 和 $(x_{2}, y_{2})$ ，那么最短距离就等于 $∣ x_{1} - y_{1} ∣ + ∣ x_{2} - y_{2} ∣$ ，也就是两者之间的曼哈顿距离。

想要证明并不难，因为一旦这个曼哈顿距离路径上存在一个障碍物，那么这个障碍物肯定属于两个集合中的一个，于是将其中一个端点替换为这个障碍物，所得到的路径肯定更短，这和假设最短距离是矛盾的，所以最短距离就是曼哈顿距离。

想到这里，我们就可以发现遍历两个集合的所有点，使用曼哈顿距离公式十年可以得到最小值的，原因很简单（最小值是使用这个公式计算的）。

接下来再想，我们应该怎么做，可以找出这两个集合？这其实有个很有名的算法，套路也很固定，叫做Flood Fill算法，即洪水覆盖算法。它有两种写法，BFS和DFS。用来求解一个图中的所有连通块，时间复杂度是 $O (m n)$ 。下面，给出这两种写法，十分巧妙！

问题的时间复杂度： $O (m n)$ ，与Flood Fill算法一致

代码

//奶牛选美，Flood Fill算法+曼哈顿距离，BFS
#include<bits/stdc++.h>

using namespace std;

typedef pair<int,int> PII;

const int N = 55;

int n, m;
char g[N][N];
bool st[N][N];

void bfs(int x, int y, vector<PII> &points)
{
    queue<PII> q;
    q.push({x, y});
    st[x][y] = true;
    
    int dx[4] = {-1,0,1,0}, dy[4] = {0,1,0,-1};
    
    while(q.size())
    {
        auto t = q.front();q.pop();
        points.push_back(t);
        
        for(int i = 0; i < 4; i++)
        {
            int a = t.first + dx[i], b = t.second + dy[i];
            
            if(a < 0 || a >= n || b < 0 || b >= m) continue;
            if(g[a][b] == '.') continue;
            if(st[a][b]) continue;
            
            q.push({a, b});
            st[a][b] = true;
        }
    }
}

int main()
{
    cin >> n >> m;

    for(int i = 0; i < n; i++) cin >> g[i];

    vector<PII> points[2];

    for(int i = 0, k = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            if(g[i][j] == 'X' && !st[i][j])
            {
                bfs(i, j, points[k++]);
            }
        }
    }

    int res = 1e8;
    for(auto &x : points[0])
        for(auto &y : points[1])
            res = min(res, abs(x.first - y.first) + abs(x.second - y.second));
    cout << res  - 1 << endl;

    return 0;
}

//Flood Fill 算法+ 曼哈顿距离 DFS
#include<bits/stdc++.h>

using namespace std;

typedef pair<int,int> PII;

const int N = 55;

int n, m;
char g[N][N];
bool st[N][N];

void dfs(int x, int y, vector<PII> &points)
{
    st[x][y] = true;
    points.push_back({x,y});
    
    int dx[4] = {-1,0,1,0}, dy[4] = {0,1,0,-1};
    
    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) continue;
        if(g[a][b] == '.') continue;
        if(st[a][b]) continue;
        
        dfs(a, b, points);
    }
}

int main()
{
    cin >> n >> m;

    for(int i = 0; i < n; i++) cin >> g[i];

    vector<PII> points[2];

    for(int i = 0, k = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            if(g[i][j] == 'X' && !st[i][j])
            {
                dfs(i, j, points[k++]);
            }
        }
    }

    int res = 1e8;
    for(auto &x : points[0])
        for(auto &y : points[1])
            res = min(res, abs(x.first - y.first) + abs(x.second - y.second));
    cout << res  - 1 << endl;

    return 0;
}