小贝子编程

我应该怎么做才能改进DFS Java实现，以解决问题



我正在尝试解决名为"墙壁和大门"的问题。

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

您将获得一个 m X n 网格，房间使用这三个可能的值初始化。

  • -1 墙壁或障碍物。

  • 0 A 门。

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

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

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

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

我的方法是

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

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

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

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

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

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

  • 然后我通过行 + 1、行 - 1、单元格 + 1、单元格 -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]
]

你的错误是你在弄清楚你是否找到了最短路径之前，你正在标记房间：

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) 可能没有效果。

快速解决方法是在呼叫结束时恢复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 给出的答案是正确的，但提供的实现，从想法上讲，与我所做的并没有太大区别，当然，除了我正在做的错误，没有正确回溯，没有再次将辅助布尔数组单元格值标记为 false，最后，它应该在所有各个边的所有遍历结束时精确地完成。

roomsBool[row][col] = false;

上述步骤至关重要，可以回溯。

另外，只需检查一次房间[行][列]小于计数：-

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也是如此，穿越风格。 因此，两个遍历的时间复杂度与上述不需要的递归调用的修剪渐近相同。

相关内容

最新更新


热门标签：

javascript python java c# php android html jquery c++ css ios sql mysql arrays asp.net json python-3.x ruby-on-rails .net sql-server django objective-c excel regex ruby linux ajax iphone xml vba spring asp.net-mvc database wordpress string postgresql wpf windows xcode bash git oracle list vb.net multithreading eclipse algorithm macos powershell visual-studio image forms numpy scala function api selenium