安排超市

分析

首先需要计算商店最少个数，每一个房子都可以前往商店购物，即'*'将地图分成了n份，那么就是n个商店（深度优先算法）
然后计算每个区域内的房子到达商店的距离和最小，也就保证了总体最小（广度优先算法）。

代码

import java.util.*;
/**
 * @author xuan
 * @date 2022/4/15 12:47
 */
public class No4 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();
        char[][] map = new char[n][n];
        char[][] map1 = new char[n][n];
        int[][] H = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int ans1 = 0;
        int ans2 = 0;
        for (int i = 0; i < n; i++) {
            map[i] = sc.nextLine().trim().toCharArray();
            map1[i] = map[i].clone();
        }
        //对每个节点进行深度优先递归统计区域个数，并且统计区域内包含的节点
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                //节点为房子需要递归。可能一个区域内没有'#'，那么不需要递归
                if (map1[i][j] == '#') {
                    ans1++; //区域个数也就是商店数量
                    List list = new ArrayList();//统计本区域内的所有节点
                    dfs(map1, i, j, list);//深度优先递归将这个区域内的节点全部遍历
                    int min = Integer.MAX_VALUE;
                    //将商店设置在coordinate,统计此区域内最小距离和
                    for (int[] coordinate : list) {
                        int min1 = 0;
                        int step = 0; //商店到节点的距离
                        //广度优先
                        boolean[][] flag = new boolean[n][n];
                        Queue queue = new LinkedList();
                        queue.offer(coordinate);
                        flag[coordinate[0]][coordinate[1]] = true;
                        while (!queue.isEmpty()) {
                            int size = queue.size();
                            for (int k = 0; k < size; k++) {
                                int[] poll = queue.poll();
                                int x = poll[0], y = poll[1];
                                //如果此节点是房子，那么需要统计距离
                                if (map[x][y] == '#') {
                                    min1 += step;
                                }
                                for (int l = 0; l < 4; l++) {
                                    int xx = x + H[l][0];
                                    int yy = y + H[l][1];
                                    //超过边界或者不是此区域或者遍历过 则不加入队列
                                    if (xx = n || yy >= n || map[xx][yy] == '*' || flag[xx][yy]) {
                                        continue;
                                    }
                                    queue.offer(new int[]{xx, yy});
                                    //标记已遍历
                                    flag[xx][yy] = true;
                                }
                            }
                            step++;
                        }
                        //求出此区域内的最小距离和
                        min = Math.min(min1, min);
                    }
                    //总的距离和
                    ans2 += min;
                }
            }
        }
        System.out.println(ans1 + " " + ans2);
    }
    /**
     * 
     * @param map 备份的地图
     * @param x 纵坐标
     * @param y 横坐标
     * @param list 统计此区域内的节点
     */
    public static void dfs(char[][] map, int x, int y, List list) {
        int n = map.length;
        if (x = n || y >= n || map[x][y] == '*') {
            return;
        }
        list.add(new int[]{x, y});
        //标记已遍历
        map[x][y] = '*';
        //遍历上下左右
        dfs(map, x - 1, y, list);
        dfs(map, x + 1, y, list);
        dfs(map, x, y - 1, list);
        dfs(map, x, y + 1, list);
    }
}

思路：先求区域，再在区域基础上求距离。
用例都过了，提交过1/5，烦请各位大佬看看有哪里搞错了，万分感谢！

#include 
#include 
#include 
#include 
using namespace std;
// 思路：首先求可连通区域，然后再在联通区域内求距离的最小值。
// BFS求联通区域内的房子和道路，cmap中存房子，cmap1中存路。
void BFS(vector& mm, int i , int j, vector>& cmap, vector>& cmap1){
    if (i = mm.size() || j = mm.size()) return;
    if (mm[i][j] == '*') return;
    if (mm[i][j] == '#') {
        cmap.push_back({i, j}); // 存房子
    }
    else if (mm[i][j] == '.'){
        cmap1.push_back({i, j}); // 存路
    }
    mm[i][j] = '*';
    BFS(mm, i + 1, j, cmap, cmap1);
    BFS(mm, i - 1, j, cmap, cmap1);
    BFS(mm, i, j + 1, cmap, cmap1);
    BFS(mm, i, j - 1, cmap, cmap1);
}
// 超市可以建在路和房子上，所以cmap和cmap1都是超市位置的候选，但只要求房子到超市的距离最小，内层循环一定遍历房子（cmap）
int disCalc(vector>& cmap, vector>& cmap1){
    int minD = INT32_MAX;
    for (int i = 0; i < cmap.size(); i++){
        int dis = 0;
        for (int j = 0; j < cmap.size(); j++){
            dis += abs(cmap[i][0] - cmap[j][0]) + abs(cmap[i][1] - cmap[j][1]); // 求距离
        }
        if (dis < minD){
            minD = dis;
        }
    }
    for (int i = 0; i < cmap1.size(); i++){
        int dis = 0;
        for (int j = 0; j < cmap.size(); j++){
            dis += abs(cmap1[i][0] - cmap[j][0]) + abs(cmap1[i][1] - cmap[j][1]);
        }
        if (dis < minD){
            minD = dis;
        }
    }
    return minD;
}
void deal(int n, vector& mat){
    vector mm(mat.begin(), mat.end());
    int cnt = 0;
    int disSum = 0;
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            if (mm[i][j] != '*'){
                vector> cmap;
                vector> cmap1;
                BFS(mm, i, j, cmap, cmap1);
                if (cmap.size() == 0){ // 如果此联通区域内无房子，自然不用再计算距离和个数
                    continue;
                }
                else{
                    int dis = disCalc(cmap, cmap1);
                    disSum += dis;
                    cnt ++;
                }
            }
        }
    }
    cout << cnt << " " << disSum << endl;
}
int main(){
    int n;
    cin >> n;
    vector mat(n);
    for (int i = 0; i < n; i++){
        cin >> mat[i];
    }
    deal(n, mat);
    return 0;
}

3
#*#             [1,1][1,2][1,3]
.**  对应的坐标   [2,1][2,2][2,3]
*.#             [3,1][3,2][3,3]

#include<iostream>
#include<vector>
#include<deque>

using namespace std;

// 区域大小
int N;

// 区域地图
char ts[50][50];

// 区域是否被访问过
// 用于第一步找出所有被隔离的区域
// 初始化设置false,被访问过设置true
bool visit[50][50];

// 区域id
// 相同的区域id，表示他们是在同一块区域
// 例如[1,1] = 1,[1,2] = 1,表示[1,1][1,2]在同一块区域内
// 初始化 -1
int field[50][50];

// 设置区域id使用，改成结构体会不会好理解点？
class tile
{
 public:
    char ch;  // '#' '.' '*'
    int i;    // 坐标
    int j;    // 坐标
    
    tile(int _i, int _j, char _ch)
    {
        i = _i;
        j = _j;
        ch = _ch;
        visit[j][i] = true;
    }
};

// 用于穷举法，计算区域内的可通行位置到达每个房子的距离之和
class result
{
public:
    bool hasSuper;   // 是否有超市（有些被隔离区域内可能没有超市）
    int minPath;     // 区域内每个房子到达超市最小距离之和
    result(bool h, int m)
    {
        hasSuper = h;
        minPath = m;
    }
};

// 题目说的要检查传参
bool isValidChar(char ch)
{
    // # 房子
    // . 道路
    // * 障碍
    return ch == '#' ||
        ch == '.' ||
        ch == '*';
}

// 设置由__t展开的区域的区域id
void fillField(tile __t, int fieldId)
{
        // 广度遍历的算法思想
        // 由__t为起点，依次遍历__t四周的所有位置
        // 可通行（道路或者房子），且没有被遍历过，纳入队列继续遍历
        // 被遍历过的所有可通行位置，就属于同一个区域。
    deque<tile> d;
    d.push_back(__t);
    while(d.size() != 0)
    {
        tile head = d.front();
        d.pop_front();
        field[head.j][head.i] = fieldId;
        
                // 左遍历
        int i = head.i - 1;
        int j = head.j;
        if (i >= 0 && !visit[j][i])
        {
            tile t(i, j, ts[j][i]);
            d.push_back(t);
        }
        
                // 右遍历
        i = head.i + 1;
        j = head.j;
        if (i < N && !visit[j][i])
        {
            tile t(i, j, ts[j][i]);
            d.push_back(t);
        }
        
                // 上遍历
        i = head.i;
        j = head.j - 1;
        if (j >= 0 && !visit[j][i])
        {
            tile t(i, j, ts[j][i]);
            d.push_back(t);
        }

                // 下遍历
         i = head.i;
        j = head.j + 1;
        if (j < N && !visit[j][i])
        {
            tile t(i, j, ts[j][i]);
            d.push_back(t);
        }
    }
}

// 穷举法找到最小距离之和
result* findMinFath(int fieldId)
{
        // 先把房子坐标找出
    int roomI[50] = {-1};
    int roomJ[50] = {-1};
    
    int index = 0;
    for(int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (field[j][i] == fieldId && ts[j][i] == '#')
            {
                roomI[index] = i;
                roomJ[index++] = j;
            }
        }
    }
    
    if(index == 0)
                // 区域内没有房子
        return new result(false, 0);
    
    result* r = NULL;
    for (int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
        {
            if (field[j][i] == fieldId)
            {
                            // 计算[j，i]位置到达所有房子的最小距离
                int path = 0;
                for(int xx = 0; xx < index; xx++)
                {
                    int diffI = roomI[xx] - i;
                    int diffJ = roomJ[xx] - j;
                    path += (diffI >= 0 ? diffI : -diffI);
                    path += (diffJ >= 0 ? diffJ : -diffJ);
                }
                
                if(r == NULL)
                    r = new result(true, path);
                else
                    r->minPath = min(r->minPath, path);
            }
        }
    }
    return r;
}

int main()
{
    cin >> N;
    for(int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> ts[j][i];
            if(!isValidChar(ts[j][i]))
            {
                                // 输入错误直接返回
                cout << "0 0" << endl;
                return 0;
            }
        }
    }

    for(int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
                        // 不可通行位置直接设置true
            bool pass = ts[j][i] == '.' || ts[j][i] == '#';
            visit[j][i] = !pass;
        }
    }

    for(int i = 0; i < N; i++)
    {
                // 初始化
        for (int j = 0; j < N; j++)
            field[j][i] = -1;
    }
    
    vector<tile> fields;
    fields.clear();
    int fieldId = 0;
    for(int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
                        // 找出被隔离区域
            if(!visit[j][i])
            {
                tile t(i, j, ts[j][i]);
                fields.push_back(t);
                fillField(t, ++fieldId);
            }
        }
    }

    int path = 0;
    int super = 0;
    for(int i = 1; i <= fieldId; i++)
    {
        result* r = findMinFath(i);
                if (r->hasSuper)
        {
                    // 有房子需要建超市
                    super++;
                    path += r->minPath;
        }
        free(r);
    }
    
    cout << super;
    cout << " ";
    cout << path << endl;
    return 0;
}