我应该如何改进我的DFS的Java实现，从而解决问题？

问题描述 投票：0回答：1

我正在尝试解决名为 Walls and Gates 的问题。

这里是问题链接。 https://leetcode.com/problems/walls-and-gates/description/

你有一个 m X n 网格，房间用这三个可能的值初始化。

  • -1 墙壁或障碍物。

  • 0 门。

  • INF无限意味着一个空房间。

    我们使用值 231 - 1 = 2147483647 来表示 INF，因为您可以假设到门的距离小于 2147483647.

用到最近大门的距离填充每个空房间。如果无法到达大门，则应填充 INF.

我正在尝试使用DFS来解决上述问题。

我的做法是

  • 使用两个索引 i 和 j 遍历网格。

  • 无论何时遇到 0 单元格值，我都会启动 DFS，因为根据问题定义，这是一个门。

  • 在DFS算法中，我首先检查边界是否满足。

    • 如果越界，我就返回。
    • 如果单元格值为 -1 那么我也会返回，因为根据问题条件它是一堵墙。
    • 如果单元格已经遍历，那么我也返回。

    经过上述所有情况，我找出单元格值和计数的最小值，并用最小值更新当前单元格。

  • 将单元格标记为已访问。为此，我正在使用另一个布尔网格。

  • 然后我遍历所有单元格，row + 1, row - 1, cell + 1, cell -1.

代码如下：

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);
                    roomsBool = new boolean[rooms.length][rooms[i].length];
                }
            }
        }
    }

    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 || roomsBool[row][col] == true || rooms[row][col] == 0 && count > 0) return;
        if(rooms[row][col] > 0){
            rooms[row][col] = Math.min(rooms[row][col], count);
        }
        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);
    }
}

问题是这段代码不正确，没有给出所需的正确结果，这个解决方案缺少什么？我应该添加什么来使这个解决方案变得万无一失？

这是问题的示例输入。

[
    [0, 2147483647, -1, 2147483647, 2147483647, -1, -1, 0, 0, -1, 2147483647, 2147483647, 0, -1, 2147483647, 2147483647, 2147483647, 2147483647, 0, 2147483647, 0, -1, -1, -1, -1, 2147483647, -1, -1, 2147483647, 2147483647, -1, -1, 0, 0, -1, 0, 0, 0, 2147483647, 0, 2147483647, -1, -1, 0, -1, 0, 0, 0, 2147483647],
    [2147483647, 0, -1, 2147483647, 0, -1, -1, -1, -1, 0, 0, 2147483647, 2147483647, -1, -1, 2147483647, -1, -1, 2147483647, 2147483647, -1, 0, -1, 2147483647, 0, 2147483647, -1, 2147483647, 0, 2147483647, 0, 2147483647, -1, 2147483647, 0, 2147483647, -1, 2147483647, 0, 2147483647, 2147483647, 0, -1, 2147483647, -1, -1, -1, 0, 2147483647]
]

这是我的输出。

[
    [0, 1, -1, 2, 1, -1, -1, 0, 0, -1, 1, 2, 0, -1, 4, 3, 2, 1, 0, 1, 0, -1, -1, -1, -1, 2, -1, -1, 1, 2, -1, -1, 0, 0, -1, 0, 0, 0, 1, 0, 2, -1, -1, 0, -1, 0, 0, 0, 1],
    [1, 0, -1, 3, 0, -1, -1, -1, -1, 0, 0, 2, 1, -1, -1, 4, -1, -1, 1, 2, -1, 0, -1, 1, 0, 1, -1, 1, 0, 1, 0, 1, -1, 1, 0, 1, -1, 1, 0, 1, 1, 0, -1, 1, -1, -1, -1, 0, 1]
]

而这里是预期的输出。

[
    [0, 1, -1, 2, 1, -1, -1, 0, 0, -1, 1, 1, 0, -1, 4, 3, 2, 1, 0, 1, 0, -1, -1, -1, -1, 2, -1, -1, 1, 2, -1, -1, 0, 0, -1, 0, 0, 0, 1, 0, 1, -1, -1, 0, -1, 0, 0, 0, 1],
    [1, 0, -1, 1, 0, -1, -1, -1, -1, 0, 0, 1, 1, -1, -1, 4, -1, -1, 1, 2, -1, 0, -1, 1, 0, 1, -1, 1, 0, 1, 0, 1, -1, 1, 0, 1, -1, 1, 0, 1, 1, 0, -1, 1, -1, -1, -1, 0, 1]
]

更多样本输入及其预期输出如下：-

  1. 样本输入
[
    [2147483647, -1, 0, 2147483647],
    [2147483647, 2147483647, 2147483647, -1],
    [2147483647, -1, 2147483647, -1],
    [0, -1, 2147483647, 2147483647]
]

样本输出1的预期输出

 [
    [3, -1, 0, 1],
    [2, 2, 1, -1],
    [1, -1, 2, -1],
    [0, -1, 3, 4]
]

样本输入 2.

[
    [-1]
]

样本输入 2 的预期输出。

[
    [-1]
]
java algorithm depth-first-search
1个回答
2
投票

你的错误是你在弄清楚你是否找到最短路径之前将房间标记为已看到：

    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);
    }

即call(1) 使 

roomsBool
中所有可到达的单元格中毒，具有 
true
值，因此，调用 (2)、(3) 和 (4) 可能无效。

Quick fix 是在 

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) {
    boolean[][] seen = 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) {
                visitRoomsDFS(rooms, i, j, 0, seen);
            }
        }
    }
}

private void visitRoomsDFS(int[][] rooms, int row, int col, int count, boolean[][] seen) {
    seen[row][col] = true;
    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;
        }
        if (seen[r][c] || rooms[r][c] < count + 1) {
            continue;
        }
        rooms[r][c] = count + 1;
        visitRoomsDFS(rooms, r, c, count + 1, seen);
    }
    seen[row][col] = false;
}

然而，即使进行了这样的优化，时间复杂度仍然是

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<>();
    boolean[][] seen = new boolean[rooms.length][rooms[0].length];
    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});
                seen[i][j] = true;
            }
        }
    }
    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;
            }
            // the wall
            if (rooms[r][c] == -1) {
                seen[r][c] = true;
            }
            // have seen before
            if (seen[r][c]) {
                continue;
            }
            // prevent adding the same room
            // to the stack multiple times
            seen[r][c] = true;
            rooms[r][c] = distance;
            deque.addLast(new int[]{r, c});
        }
    }
}
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.