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

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

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

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

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

【输入样例】

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

【输出样例】

3 

【分析】

【朴素解法代码】

#include <iostream> #include <cstring> #include <algorithm> #include <vector> using namespace std; typedef pair<int, int> PII; const int N = 60; char g[N][N]; int n, m, cnt; vector<PII> v[2];//存储连通块中的所有点 int dx[4] = { 
      -1, 0, 1, 0 }, dy[4] = { 
      0, 1, 0, -1 }; void dfs(int x, int y, vector<PII>& 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 <iostream> #include <cstring> #include <algorithm> #include <deque> #define X first #define Y second using namespace std; typedef pair<int, int> 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 (x < 0 || x >= n || y < 0 || y >= m || st[x][y] || g[x][y] != 'X') 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, -1, sizeof dis); dis[sx][sy] = 0; deque<PII> Q; Q.push_back({ 
      sx, sy }); while (Q.size()) { 
      auto t = Q.front(); Q.pop_front(); if (t.X == gx && t.Y == gy) return dis[gx][gy]; for (int i = 0; i < 4; i++) { 
      int nx = t.X + dx[i], ny = t.Y + dy[i]; if (nx >= 0 && nx < n && ny >= 0 && ny < m && !~dis[nx][ny]) { 
      int w = g[nx][ny] == '.'; dis[nx][ny] = dis[t.X][t.Y] + w; if (w) Q.push_back({ 
      nx, ny }); else Q.push_front({ 
      nx, ny }); } } } return -1; } 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 (!st[i][j] && g[i][j] == 'X') p[cnt++] = { 
      i, j }, dfs(i, j); cout << bfs(p[0].X, p[0].Y, p[1].X, p[1].Y) << endl; return 0; }