Максимальное значение среди кратчайших расстояний в матрице

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 и 2, добавляя 1 каждый раз, когда мы перемещаемся по горизонтали и / или по вертикали.Обратите внимание, что диагональное перемещение недопустимо:

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

Мне не удалось написать какой-либо код, потому что, честно говоря, я не смог вывести решение.

Если две указанные точки являются фиксированными точкамив 2d матрице я могу найти расстояние или кратчайшее расстояние между ними.Но, в этом случае, я не знаю, где будут две точки?Там может быть много оптимальных решений и размещение комбинаций 0 в каждом месте, и найти самое дальнее расстояние невозможно и не будет возможным.Я попытался разместить их на позициях, которые дают максимальное количество 1 (например, среднее или w / 2), но это, похоже, тоже не работает.Может ли существующий алгоритм быть применен к этой проблеме?

Answer 1

Java Solution без битовой маски и необходимости запоминания путем передачи позиций на рекурсивные вызовы

class MaximumShortestDist
{
    static int[] dx = new int[]{1, -1, 0, 0};
    static int[] dy = new int[]{0, 0, -1, 1};

    public static void main(String[] args) {
        System.out.println(findMinDist(14,2,5));
    }

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

        int[][] grid = new int[w][h];
        for(int i=0;i<w;i++)
            Arrays.fill(grid[i],-1);
        return solve(n,w,h,0,0,grid);
    }

    static int bfs(int W, int H, int[][] grid) {

        int[][] dist = new int[W][H];
        for(int i=0;i<W;i++)
            for(int j=0;j<H;j++)
                dist[i][j] = grid[i][j];

        int maxDist = 0;
        Queue<Location> Q = new LinkedList<>();
        for(int i = 0; i < W; i++)
            for(int j = 0; j < H; j++)
                if(dist[i][j] == 0){
                    Q.add(new Location(i,j));
                }

        while(!Q.isEmpty()) {
            int x = Q.peek().first;
            int y = Q.peek().second;
            maxDist = Math.max(maxDist, dist[x][y]);
            Q.poll();

            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.add(new Location(newx, newy));
                }
            }
        }
        return maxDist;
    }

    static int solve(int left, int W, int H, int row, int col,int[][] grid) {
        if(left == 0) {
            return bfs(W,H,grid);
        }
        int r = row,c=col;
        if(col >= H) {
            r += col/H;
            c = col%H;
        }
        int minDistance = Integer.MAX_VALUE;
        for(int i=r;i<W;i++){
            for(int j=c;j<H;j++) {
                //Mark Building locations in the recursive call.
                grid[i][j] = 0;
                int val = solve(left-1, W, H,i,j+1,grid);
                minDistance = Math.min(minDistance, val);
                // Remove the building
                grid[i][j] = -1;
            }
        }
        return minDistance;
    }
}


class Location {
    int first;
    int second;
    Location(int x, int y) {
        first = x;
        second = y;
    }
}

Answer 2

Я пытался решить этот вопрос с помощью Python.Суть ответа лежит в моей пошаговой функции, которая получает все возможные положения N зданий в сетке W x H и выдает результат в виде списка.Каждая позиция в списке является местоположением в W * i + H. То есть позиции в 2x2 рассматриваются как 0, 1, 2, 3.

# generator function to give each building position 
# in a W x H grid
def step(W, H, N):
    dim = W * H
    slots = [n for n in range(N)]
    slots_temp = list(slots)
    persist = list(slots)
    last = [dim - n for n in slots]
    last = last[::-1]
    while slots != [0] * N:
        yield slots
        for i in range(len(slots)-1,-1,-1):
            slots[i]+=1
            if slots[i] >= last[i] :
                slots[i] = 0
            else:
                while i < len(slots)-1:
                    slots[i+1] = slots[i] + 1
                    i+=1
                break

# converts a ixj to a step
# assumes W <= H
def get_step(i, j, W , H):
    return (i * W) + j

# does bfs from each building position
# and gets the maximum distance 
def bfs(step,W,H):
    dist = [[-1]*H for i in range(W)]
    queue = []
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    for i in range(W):
        for j in range(H):
            step_val = get_step(i, j, W, H)
            if step_val in step:
                dist[i][j] = 0
                queue.append((i,j))
    max_val = 0
    while len(queue) != 0:
        i,j = queue.pop(0)
        max_val = max(max_val, dist[i][j])
        for _dx,_dy in zip(dx,dy):
            new_i,new_j = i + _dx, j + _dy
            if new_i < 0 or new_i >= W or new_j <0 or new_j >= H:
                continue
            if dist[new_i][new_j] == -1:
                dist[new_i][new_j] = dist[i][j] + 1
                queue.append((new_i,new_j))
    return max_val


# calls each posible position of the building
# and computes the minimum distance of all
def main(W, H, N ): 
    min_val = float('inf')
    if W > H:
        W, H = H, W
    s = step(W, H, N)
    for slot in s:
        b = bfs(slot, W, H)
        min_val = min(min_val, b)
    return min_val



main(4, 4, 2)

Answer 3

Java-код для этого без побитовых операций.

import javafx.util.Pair;
import java.util.*;

class Office_N {
    // W for width, H for height, N for no of offices to build
    int W, H, N;

    // dx and dy value together gives (x,y)
    // which helps to move in 4 adjacent cells
    // Right (1,0)
    // Left (-1,0)
    // Down (0,1)
    // Up (0,-1)
    int[] dx = {1, -1, 0, 0};
    int[] dy = {0, 0, 1, -1};
    Map<String, Integer> dp = new HashMap<>();

    int[][] grid;

    // Constructor will set the values and clear the hashmap.
    public Office_N(int w, int h, int n) {
        W = w;
        H = h;
        N = n;
        dp.clear();
        grid = new int[W][H];

        for (int[] r : grid) {
            Arrays.fill(r, 0);
        }
    }

    // We convert the 2D array of W*H into 1D array in Row Order (if square matrix or Width is less),
    // or Column Wise (if Height is less)
    // BitMask holds the bits 0 empty spots, and 1 for where offices are present
    // Left means how many offices are still left to be built
    public int solve(int[][] grid, int left) {

        // If no more offices are left to be built, get the maximum distance for this scenario
        if (left == 0) {
            return bfs(grid);
        }

        StringBuilder k = new StringBuilder();

        for (int i = 0; i < W; i++) {
            for (int j = 0; j < H; j++) {
                if (grid[i][j] == 1) {
                    k.append(i + ":" + j + "::");
                }
            }
        }

        k.append("#" + left);
        // if the current scenario along with offices left are already processed, return the result
        String key = k.toString();
        if (dp.containsKey(key)) {
            return dp.get(key);
        }

        int[][] gridtemp = new int[W][H];
        for (int i = 0; i < W; i++) {
            for (int j = 0; j < H; j++) {
                gridtemp[i][j] = grid[i][j];
            }
        }

        //  We are trying every possible scenario to build offices in the given grid
        int minDist = Integer.MAX_VALUE;
        for (int i = 0; i < W; i++) {
            for (int j = 0; j < H; j++) {
                // If no office present in (i,j)th location, put one office there and check the minimum distance for that scenario
                if (gridtemp[i][j] == 0) {
                    gridtemp[i][j] = 1;
                    int val = solve(gridtemp, left - 1);
                    minDist = Math.min(minDist, val);
                    gridtemp[i][j] = 0;
                }
            }
        }

        // Store the min distance possible for the current scenario
        dp.put(key, minDist);
        return minDist;
    }

    // This function gives the maximum distance from all the empty spots to the offices for a given case of scenario
    private int bfs(int[][] grid) {
        // get a distance matrix with initial values as -1
        int[][] dist = new int[W][H];
        for (int[] row : dist)
            Arrays.fill(row, -1);

        int maxDist = 0;
        // Queue for processing the cells in Bredth-First-Search order.
        Queue<Pair<Integer, Integer>> Q = new LinkedList<>();

        // if office is present at (i,j)th location, the distance is 0, and put the (i,j) pair in Queue
        for (int i = 0; i < W; i++) {
            for (int j = 0; j < H; j++) {
                if (grid[i][j] == 1) {
                    dist[i][j] = 0;
                    Q.add(new Pair<>(i, j));
                }
            }
        }


        while (!Q.isEmpty()) {
            Pair<Integer, Integer> kv = Q.poll();
            int x = kv.getKey();
            int y = kv.getValue();

            // Get maximum distance for (i,j)th location
            maxDist = Math.max(maxDist, dist[x][y]);

            // Process all adjacent cells
            for (int d = 0; d < dx.length; d++) {
                int xNew = x + dx[d];
                int yNew = y + dy[d];

                // if the adjacent cell is within grid boundary, and is not yet processed,
                // set the max dist of he adjacent cell 1 more than the (i,j)th cell
                // add the adjacent cell to queue
                if (xNew >= 0 && xNew < W && yNew >= 0 && yNew < H && dist[xNew][yNew] == -1) {
                    dist[xNew][yNew] = dist[x][y] + 1;
                    Q.add(new Pair<>(xNew, yNew));
                }
            }
        }

        return maxDist;
    }

    public static void main(String[] args) {
        Office_N ofc = new Office_N(4, 4, 3);
        int res = ofc.solve(ofc.grid, ofc.N);
        System.out.println(res);
    }
}

Answer 4

Согласно данному ограничению, размер матрицы ( w * h ) не может превышать 28, что является довольно небольшим числом.Кроме того, максимально возможное значение для n равно 5. Из небольшого знания комбинаторики мы знаем, что есть ²⁸ C ₅ способов выбора 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;
}