algorithm - 矩阵中最短距离中的最大值

Question

我试图解决以下问题，但还没有开发出算法或方法。我研究了几个小时，试图将问题映射到“最短路径”图/矩阵问题或动态规划问题，但都没有成功。
给定一个宽度为w，高度为h的网格。网格的每个单元代表一个潜在的建筑地段，我们将在这个网格内添加“n”个建筑。
目标是所有地段中最远的地段尽可能靠近建筑物。
给定一个输入n（要放置在地块中的建筑物数量），确定建筑物放置位置，以最小化最远的空地块与建筑物的距离。
移动仅限于水平和垂直方向，即不需要对角线移动。
例如，w=4, h=4 and n=3。一个最佳的网格布局可以在建筑的两个单位距离内设置任何地块。这个案子的答案是2。
“0”表示最佳的建筑物布置，在这种情况下，每个单元的最短建筑物的所有最短距离的最大值是“2”。

1 0 1 2
2 1 2 1
1 0 1 0
2 1 2 1

上面的表示了一个最优解，有可能更像上面的数组旋转作为一个例子。
以上是一个最优的解决方案，因为在3栋建筑（n=3）中，一栋建筑位于索引（0,1）处，第二栋建筑位于索引（2,1）处，第三栋建筑位于索引（2,3）处。通过每次水平和/或垂直移动时添加1，将周围的水平和垂直距离显示为1和2。再次注意，不允许对角线移动：

1 ← 0 → 1 → 2
    ↓
2 ← 1 → 2 ← 1
    ↑       ↑
1 ← 0 → 1 ← 0
    ↓       ↓
2 ← 1 → 2 ← 1

其他示例：
例1）

w=3, h=3, n=2

两座建筑物（零）必须以最佳方式放置。这种情况下的最佳方案之一是：

01
11
10

0 → 1
↓
1   1
    ↑  
1 ← 0

Answer: 1

作为一个例子，在这种情况下，下面的计划将不是最优的，因为它的最大最小距离为2而不是1。因此，将0贪婪地放在索引（1，0）上不起作用，即使在本例中0覆盖了三个“1”位置，而不是上面的最优方案中的两个位置。

1 → 2
↑
0 → 1
↓   ↑   
1 ← 0

例2）

w=5, h=1, n=1

一栋楼（零）必须以最佳方式放置。最佳计划之一：

2 ← 1 ← 0 → 1 → 2

Answer: 2

以上场景中的非最优计划示例：

3 ← 2 ← 1 ← 0 → 1

应完成以下功能：

int findMinDist(int w, int h, int n)
{

}

限制条件：

1<=w,h
w*h <=28
1<=n<=5
n<=w*h

我没能写任何代码，因为老实说，我没能推导出解决方案。
如果两个给定点是二维矩阵中的不动点，我可以找到两者之间的距离或最短距离。但是，在这种情况下，我不知道这两点会在哪里？可能有许多最优解，在每个位置放置0的组合，并且不可能也不可能找到最远的距离。
我试着把它们放置在最大产量1的位置（比如中间或W／2），但这似乎也不起作用。
现有的算法可以应用于这个问题吗？

Answer 1

根据给定的约束条件，矩阵大小（w*h）不能超过28，这是一个相当小的数字。此外，n的最大可能值是5。从组合学的一些知识中，我们知道有28C5种方法可以在最坏的情况下从给定的网格中选择5个批次。这个数字的计算结果是98280，这是一个足够小的空间搜索与备忘录。因为W*H的最大值是28，所以我们可以在一个整数位掩码中表示整个网格，连同要设置的建筑块的数量将形成DP的状态。为了计算最终状态的最远剩余批次，我们使用广度优先搜索（bfs）来初始化队列，其中包含所有已建立建筑的点。共享运行速度足够快的代码https://ideone.com/ix1nh8

int W, H, N;

int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, -1, 1};

int calc(int i, int j) {
    if(W <= H)
        return  i + W * j;
    return H * i + j;
}

bool get(int bitmask, int i, int j) {
    return (bitmask&(1<<calc(i,j)));
}

int bfs(int bitmask) {
    int dist[W][H];
    memset(dist, -1, sizeof dist);

    int maxDist = 0;
    queue<pair<int,int>> Q;

    for(int i = 0; i < W; i++)
        for(int j = 0; j < H; j++)
            if(get(bitmask, i, j)) {
                dist[i][j] = 0;
                Q.push({i, j});
            }
    assert(Q.size() == N);

    while(!Q.empty()) {
        int x = Q.front().first;
        int y = Q.front().second;
        maxDist = max(maxDist, dist[x][y]);
        Q.pop();

        for(int d = 0; d < 4; d++) {
            int newx = x + dx[d];
            int newy = y + dy[d];

            if(newx >= W || newy >= H || newx < 0 || newy < 0)
                continue;
            if(dist[newx][newy] == -1) {
                dist[newx][newy] = dist[x][y] + 1;
                Q.push({newx, newy});
            }
        }
    }
    return maxDist;
}

map<pair<int,int>, int> dp;

int solve(int bitmask, int left) {
    if(left == 0) {
        return bfs(bitmask);
    }
    if(dp.find({bitmask, left}) != dp.end()) {
        return dp[{bitmask, left}];
    }
    int minDistance = INT_MAX;
    for(int i = 0; i < W; i++)
        for(int j = 0; j < H; j++)
            if(!get(bitmask, i, j)) {
                int val = solve((bitmask|(1<<calc(i, j))), left-1);
                minDistance = min(minDistance, val);
            }
    return dp[{bitmask, left}] = minDistance;
}