AcWing 2060. 奶牛选美（双端队列BFS）

AcWing 2060. 奶牛选美（双端队列BFS）

【题目描述】
听说最近两斑点的奶牛最受欢迎，约翰立即购进了一批两斑点牛。
不幸的是，时尚潮流往往变化很快，当前最受欢迎的牛变成了一斑点牛。
约翰希望通过给每头奶牛涂色，使得它们身上的两个斑点能够合为一个斑点，让它们能够更加时尚。
牛皮可用一个 N × M N×M N×M的字符矩阵来表示，如下所示：

................
..XXXX....XXX...
...XXXX....XX...
.XXXX......XXX..
........XXXXX...
.........XXX....

其中，X表示斑点部分。
如果两个X在垂直或水平方向上相邻（对角相邻不算在内），则它们属于同一个斑点，由此看出上图中恰好有两个斑点。
约翰牛群里所有的牛都有两个斑点。
约翰希望通过使用油漆给奶牛尽可能少的区域内涂色，将两个斑点合为一个。
在上面的例子中，他只需要给三个 . 区域内涂色即可（新涂色区域用∗表示）：

................
..XXXX....XXX...
...XXXX*...XX...
.XXXX..**..XXX..
........XXXXX...
.........XXX....

请帮助约翰确定，为了使两个斑点合为一个，他需要涂色区域的最少数量。

【输入格式】
第一行包含两个整数 N N N和 M M M。
接下来 N N N行，每行包含一个长度为 M M M的由X和.构成的字符串，用来表示描述牛皮图案的字符矩阵。

【输出格式】
输出需要涂色区域的最少数量。

【数据范围】
1 ≤ N , M ≤ 50 1≤N,M≤50 1≤N,M≤50

【输入样例】

6 16
................
..XXXX....XXX...
...XXXX....XX...
.XXXX......XXX..
........XXXXX...
.........XXX....

【输出样例】

3

【分析】

---

朴素解法：
观察到数据范围很小，因此其中一种思路是先将两个连通块的所有点找出来，然后遍历所有点对，在所有点对的曼哈顿距离中选出最小的即为两个连通块的最短距离，由于走到另一个连通块的最后一步不需要算入步数，因此两点间的距离计算要注意减一。

双端队列BFS解法：
使用双端队列BFS，我们只需要求出某个连通块中的任意一点到另一个连通块中的任意一点的最短距离即可。在移动的时候，如果移动到X上，则距离 + 0 +0 +0，插入到双端队列头部；如果移动到.上，则距离 + 1 +1 +1，插入到双端队列尾部。这样即可求出两个连通块间的最短距离。

---

【朴素解法代码】

#include 
#include 
#include 
#include 
using namespace std;

typedef pair PII;
const int N = 60;
char g[N][N];
int n, m, cnt;
vector v[2];//存储连通块中的所有点
int dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, 1, 0, -1 };

void dfs(int x, int y, vector& v)
{
    if (x < 0 || x >= n || y < 0 || y >= m || g[x][y] == '.') return;
    g[x][y] = '.';
    v.push_back({ x, y });
    for (int i = 0; i < 4; i++) dfs(x + dx[i], y + dy[i], v);
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> g[i];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (g[i][j] == 'X') dfs(i, j, v[cnt++]);
    int res = 0x3f3f3f3f;
    for (auto x : v[0])
        for (auto y : v[1])
            res = min(res, abs(x.first - y.first) + abs(x.second - y.second) - 1);
    cout << res << endl;
    return 0;
}

【双端队列解法代码】

#include 
#include 
#include 
#include 
using namespace std;

typedef pair PII;
const int N = 60;
PII p[2];
char g[N][N];
bool st[N][N];
int n, m, cnt, dis[N][N];
int dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, 1, 0, -1 };

void dfs(int x, int y)
{
    if (st[x][y] || g[x][y] == '.' || x < 0 || x >= n || y < 0 || y >= m) return;
    st[x][y] = true;
    for (int i = 0; i < 4; i++) dfs(x + dx[i], y + dy[i]);
}

//只需求出某一连通块中任一点到另一连通块中任一点的最短距离即可
int bfs(int sx, int sy, int gx, int gy)
{
    memset(dis, 0x3f, sizeof dis);
    deque Q;
    Q.push_back({ sx, sy });
    dis[sx][sy] = 0;
    while (Q.size())
    {
        auto t = Q.front();
        Q.pop_front();
        if (t.first == gx && t.second == gy) return dis[gx][gy];
        for (int i = 0; i < 4; i++)
        {
            int nx = t.first + dx[i], ny = t.second + dy[i];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && dis[nx][ny] == 0x3f3f3f3f)
            {
                int w = g[nx][ny] == '.';//如果走到.上则距离+1
                dis[nx][ny] = dis[t.first][t.second] + w;
                if (!w) Q.push_front({ nx, ny });
                else Q.push_back({ nx, ny });
            }
        }
    }
    return 20030925;
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> g[i];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (g[i][j] == 'X' && !st[i][j]) p[cnt++] = { i, j }, dfs(i, j);
    cout << bfs(p[0].first, p[0].second, p[1].first, p[1].second) << endl;
    return 0;
}