Что я должен сделать, чтобы улучшить реализацию DFS Java, чтобы решить проблему?

Ваша ошибка в том, что вы отмечаете комнату, как видно, прежде чем выяснять, нашли ли вы кратчайший путь или нет:

    private void visitRommsDFS(int[][] rooms, int row, int col, int count, boolean[][] roomsBool){
        if (... roomsBool[row][col] == true ...) {
            return;
        }
        if (rooms[row][col] > 0){
            rooms[row][col] = Math.min(rooms[row][col], count);
        }
        roomsBool[row][col] = true;
        // 1
        visitRommsDFS(rooms, row-1, col, count + 1, roomsBool);
        // 2
        visitRommsDFS(rooms, row+1, col, count + 1, roomsBool);
        // 3
        visitRommsDFS(rooms, row, col+1, count + 1, roomsBool);
        // 4
        visitRommsDFS(rooms, row, col-1, count + 1, roomsBool);
    }

то есть вызов (1) отравляет все достижимые ячейки в roomsBool значением true, поэтому вызовы (2), (3) и (4) могут не иметь никакого эффекта.

Быстрое решение состоит в том, чтобы вернуть roomsBool состояние обратно в конце visitRommsDFS вызова:

roomsBool[row][col] = true;
visitRommsDFS(rooms, row - 1, col, count + 1, roomsBool);
visitRommsDFS(rooms, row + 1, col, count + 1, roomsBool);
visitRommsDFS(rooms, row, col + 1, count + 1, roomsBool);
visitRommsDFS(rooms, row, col - 1, count + 1, roomsBool);
roomsBool[row][col] = false;

Ну... Кстати, я не уверен, что стоит пытаться оптимизировать эту головоломку без соответствующих тестовых данных...

ваш текущий алгоритм: пусть найдут все комнаты с воротами и пройдут все комнаты, до которых можно добраться от определенных ворот, временная сложность для такого наивного алгоритма явно хуже, чем O(MxNxG), лучшее, что вы можете здесь получить, это прекратить обход комнат, если комната ближе к «другой». ворота, а не к текущему, что-то вроде:

public static final int[][] DIRS = new int[][]{new int[]{-1, 0}, new int[]{1, 0}, new int[]{0, -1}, new int[]{0, 1}};

public void wallsAndGates(int[][] rooms) {
    for (int i = 0; i < rooms.length; ++i) {
        for (int j = 0; j < rooms[i].length; ++j) {
            if (rooms[i][j] == 0) {
                visitRoomsDFS(rooms, i, j);
            }
        }
    }
}

private void visitRoomsDFS(int[][] rooms, int row, int col) {
    int distance = rooms[row][col] + 1;
    for (int[] dir : DIRS) {
        int r = row + dir[0];
        int c = col + dir[1];
        if (r < 0 || c < 0 || r >= rooms.length || c >= rooms[row].length) {
            continue;
        }
        // optimization: "have seen better" or not a room
        if (rooms[r][c] <= distance) {
            continue;
        }
        rooms[r][c] = distance;
        visitRoomsDFS(rooms, r, c);
    }

}

Однако я считаю, что даже при такой оптимизации временная сложность все равно не лучше O(MxNxG), с другой стороны теоретическая временная сложность для этой головоломки не должна быть лучше O(MxN) - нам все равно нужно обойти все комнаты, а проблема в том, что алгоритм с временной сложностью O(MxN) существует:

основная идея состоит в том, чтобы проходить комнаты в очень определенном порядке:

• сначала проходим через ворота
• через секунду пересекаем соседей ворот - такие комнаты либо имеют расстояние 1 до каких-то ворот, либо являются стенами, либо мы их уже видели
• в третьем обходим всех соседей комнат, находящихся на расстоянии 1 до каких-то ворот - такие комнаты либо имеют расстояние 2 до каких-то ворот, либо являются стенами, либо мы их уже видели.
• и т. д.

public static final int[][] DIRS = new int[][]{new int[]{-1, 0}, new int[]{1, 0}, new int[]{0, -1}, new int[]{0, 1}};

public void wallsAndGates(int[][] rooms) {
    int rows = rooms.length;
    int cols = rooms[0].length;
    Deque<int[]> deque = new LinkedList<>();
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            if (rooms[i][j] == 0) {
                deque.add(new int[]{i, j});
            }
        }
    }
    int[] room;
    while ((room = deque.pollFirst()) != null) {
        int distance = rooms[room[0]][room[1]] + 1;
        for (int[] dir : DIRS) {
            int r = room[0] + dir[0];
            int c = room[1] + dir[1];
            if (r < 0 || c < 0 || r >= rows || c >= cols) {
                continue;
            }
            // ignoring walls and rooms
            // seen previously
            if (rooms[r][c] > distance) {
                rooms[r][c] = distance;
                deque.addLast(new int[]{r, c});
            }
        }
    }
}

Ответ, данный @Andrey B. Panfilov, правильный, но предоставленная реализация, по идее, не очень отличается от того, что я сделал, за исключением, конечно, ошибки, которую я делал, не возвращаясь правильно, не снова пометив значение ячейки вспомогательного логического массива как ложное в конце, это нужно сделать именно в конце всех обходов со всех сторон.

roomsBool[row][col] = false;

Этот выше шаг имеет решающее значение, чтобы вернуться.

Кроме того, всего одна проверка, что room[row][col] меньше count :-

if (rooms[row][col] < count) {
  rooms[row][col] = count;
}

не будет гарантировать, что в этой ячейке хранится наименьшее значение, мы должны позволить рекурсии решить это, какой из них является кратчайшим путем, это будет сделано, когда мы рекурсивно перейдем к ячейке с разных направлений, и чтобы включить рекурсию, выполните то, то есть позволить ему прийти с разных сторон к рассматриваемой ячейке, мы должны сделать

roomsBool[row][col] = false;

после обхода во всех 4-х направлениях.

И предложенная оптимизация может быть легко включена в мое решение. Вот полное рабочее решение.

  class Solution {
    public void wallsAndGates(int[][] rooms) {

        boolean[][] roomsBool = new boolean[rooms.length][rooms[0].length];

        for(int i = 0; i < rooms.length; ++i){
            for(int j = 0; j < rooms[i].length; ++j){
                if (rooms[i][j] == 0){
                    //if it is a gate we will do a DFS and fill the cells with the appropriate values.
                    visitRommsDFS(rooms, i, j, 0, roomsBool);
                }
            }
        }
    }

    private void visitRommsDFS(int[][] rooms, int row, int col, int count, boolean[][] roomsBool){
        if (row < 0 || row >= rooms.length || col < 0 || col >= rooms[row].length || rooms[row][col] == -1 || rooms[row][col] == 0 && count > 0) return;

        rooms[row][col] =  count;
        roomsBool[row][col] = true;

        if (row > 0 && rooms[row-1][col] > count + 1)
          visitRommsDFS(rooms, row-1, col, count + 1, roomsBool);

        if (row + 1 < rooms.length && rooms[row+1][col] > count + 1)  
          visitRommsDFS(rooms, row+1, col, count + 1, roomsBool);

        if (col + 1 < rooms[row].length && rooms[row][col + 1] > count + 1)  
          visitRommsDFS(rooms, row, col+1, count + 1, roomsBool);

        if (col > 0 && rooms[row][col - 1] > count + 1) 
          visitRommsDFS(rooms, row, col-1, count + 1, roomsBool);

        roomsBool[row][col] = false;
    }
 }

По моему скромному мнению, мораль этой истории состоит в том, чтобы возвращаться определенно, возвращаться явно, возвращаться навсегда, но возвращаться выборочно и делать это с умом.

Анализ временной сложности Поскольку пространство поиска представляет собой сетку m X n, сложность DFS, вторая вспомогательная функция равна O (m X n), так как мы покрываем все ячейки сетки, а их m X n. А обрезка, когда мы делаем рекурсивный вызов, гарантирует, что при выполнении DFS больше не будет повторяться обход ячейки.

Если бы я сделал это в BFS, то и временная сложность осталась бы такой же, как O (m X n), здесь выбор BFS и DFS не имел бы значения для временной сложности, так как размер сетки фиксируется заранее и мы проходим каждую ячейку только один раз, если только значение расстояния не меньше.

Если значение расстояния в следующем вызове меньше, чем текущее значение в ячейке, то, очевидно, мы обходим ячейку более 1 раза.

Двигаемся ли мы от центра к все большему и большему концентрическому кругу или слишком углубляемся в одном направлении, в данном случае это не повлияет на сложность.

Почему?

Поскольку количество ячеек в заданной сетке ограничено, и даже если DFS движется в одном направлении, она вынуждена вернуться из этого направления из-за краев и стенок сетки. И продолжить исследование в другом направлении, и в итоге DFS покроет все ячейки. Кроме того, благодаря логике сокращения ненужного обхода мы эффективны при обходе. Как и BFS, стиль обхода. Таким образом, временная сложность обоих обходов асимптотически одинакова с приведенным выше сокращением нежелательных рекурсивных вызовов.