题解 | #安排超市#

1. 思路

• 障碍物将整个地图分成多个区域。

• 使用 dfs求得区域数量，区域内含有住房则需要安排超市， 即含有住房的区域数即为需要安排的超市数。

• 使用bfs 枚举区域内的所有点(x,y)，求在(x, y) 安排超市时，该区域内所有房子到达(x,y)的总距离，最终选取最小值加到结果。 对所有的区域进行同样的操作。

2. 代码实现

#include <bits/stdc++.h>
int dirs[4][2] = {-1, 0, 1, 0, 0, - 1, 0, 1};

using namespace std;

int n, vis[53][53] = {}, vis2[53][53];
string grid[53];
vector<pair<int, int>> area;    // 用来存放每个区域内点的坐标

void dfs(int x, int y) {
    vis[x][y] = true;
    for (auto [dx, dy] : dirs) {
        int nx = x + dx, ny = y + dy;
        area.emplace_back(x, y);
        if (nx >= 0 && nx < n && ny >= 0 && ny < n && grid[nx][ny] != '*' && !vis[nx][ny])
            dfs(nx, ny);
    }
}

int main() {
    int res = 0, buildCnt = 0;
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> grid[i];
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (grid[i][j] == '#' && !vis[i][j]) {	// 	只有区域内存在房子才会安排超市
                ++buildCnt;	// 需要在该区域安排一个超市
                area.clear();   // 清空
                dfs(i, j);
                int d = INT_MAX;
                for (auto &[x, y] : area) {  // 求(x, y)做为该区域的超市时，所有房子到该超市的距离，枚举所有点取最小值
                    int cur = 0, step = 0;
                    memset(vis2, 0, sizeof(vis2));  // 初始化标记数组
                    queue<pair<int, int>> q;
                    q.emplace(x, y);    vis2[x][y] = true;
                    while (!q.empty()) {
                        int size = q.size();
                        for (int i = 0; i < size; ++i) {
                            auto [xx, yy] = q.front(); q.pop();
                            if (grid[xx][yy] == '#') cur += step;
                            for (auto [dx, dy] : dirs) {
                                int nx = xx + dx, ny = yy + dy;
                                if (nx >= 0 && nx < n && ny >= 0 && ny < n && grid[nx][ny] != '*' && !vis2[nx][ny]) {
                                    vis2[nx][ny] = true;
                                    q.emplace(nx, ny);
                                }
                            }
                        }
                        ++step;
                    }
                    d = min(d, cur);
                }
                res += d;
            }
        }
    }
    cout << buildCnt << ' ' << res << endl;
    return 0;
}