BFS算法在LeetCode的腐烂橙子问题中未标记所有节点。

huangapple go评论72阅读模式
英文:

BFS algorithm does not mark all nodes in the Rotten Oranges problem on Leetcode

问题

我正在解决腐烂橙子问题

在给定的网格中,每个单元格可以有三个值之一:

  • 值为0表示空单元格;
  • 值为1表示新鲜橙子;
  • 值为2表示腐烂的橙子。

每一分钟,与腐烂橙子相邻(4个方向)的任何新鲜橙子都会腐烂。

返回必须经过的最少分钟数,直到没有单元格含有新鲜橙子为止。如果不可能实现这一点,则返回-1。

示例1:

  • 输入:[[1,1,1],[1,1,0],[0,1,2]]
  • 输出:4

我已经实现了一个广度优先搜索(BFS)的解决方案。在完成BFS后,我启动另一个迭代,以确保没有新鲜橙子留下,因为如果还有新鲜橙子剩下,我就必须返回-1。

然而,我发现在最后的循环中,只有一些值被更改为2,而其他一些值仍然保持为1。我不确定为什么它们没有被改变为2。

class Solution {
    // ...
}

我的代码对上述引用的示例输出-1,因为在最终循环中仍然找到了一个1,尽管不应该有。

你能帮我找出为什么会发生这种情况吗?

英文:

I am working on the rotten oranges problem:

> In a given grid, each cell can have one of three values:
>
> * the value 0 representing an empty cell;
> * the value 1 representing a fresh orange;
> * the value 2 representing a rotten orange.
>
> Every minute, any fresh orange that is adjacent (4-directionally) to a
> rotten orange becomes rotten.
>
> Return the minimum number of minutes that must elapse until no cell
> has a fresh orange. If this is impossible, return -1 instead.
>
> ## Example 1:
>
> * Input: [[1,1,1],[1,1,0],[0,1,2]]
> * Output: 4

I've implemented a BFS solution. Then after finishing the BFS, I initiate another iteration to make sure that there's no fresh orange left, because if there are fresh oranges left over, then I have to return -1.

However, I find that in that final loop only some of the values were changed into 2, and some others remain at 1. I'm not sure why they are not changed to 2 as well.

class Solution {
    public int orangesRotting(int[][] grid) {
        //need adjacency list/matrix
        Queue<String> q = new LinkedList<>();
        int[] count = new int[1];
        count[0] = 0;
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[i].length; j++) {
                if(grid[i][j] == 2) {
                    q.add("" + i + j);
                    bfs(grid, i, j, count, q);
                }
            }
        }
        
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[i].length; j++) {
                // does NOT always print correct value: 1 is not changed to 2
                System.out.println(grid[i][j]); 
                if(grid[i][j] == 1) {
                    return -1;  // ... and so this -1 is returned when it shouldn't
                }
            }
        }
        
        return count[0];
    }
    
    private static void bfs(int[][] grid, int i, int j, int[] count,  Queue<String> q) {
        while(!q.isEmpty()) {
            String s = q.remove();
            //System.out.println(s); //prints correct indices
            i = Integer.parseInt(s.substring(0,1));
            j = Integer.parseInt(s.substring(1));
            
            if(i - 1 > 0 && grid[i - 1][j] == 1) {
                count[0]++;
                i--;
                grid[i][j] = 2;
                q.add("" + i + j);
            }
            if(i + 1 < grid.length && grid[i + 1][j] == 1) {
                count[0]++;
                i++;
                grid[i][j] = 2;
                q.add("" + i + j);
            }
            if(j - 1 > 0 && grid[i][j - 1] == 1) {
                count[0]++;
                j--;
                grid[i][j] = 2;
                q.add("" + i + j);
            }
            if(j + 1 < grid.length && grid[i][j + 1] == 1) {
                count[0]++;
                j++;
                grid[i][j] = 2;
                q.add("" + i + j);
            }
        }
        
    }
    
}

My code outputs -1 for the above quoted example, because it still finds a 1 in the final loop, while it shouldn't.

Could you help me figure out why this is happening?

答案1

得分: 0

几个问题:

  • 第0列或第0行的单元格从未被检查是否感染了橙子。比较i - 1 > 0i等于1时不成立,但你也应该检查grid[0][j]... j也有同样的问题。

  • 通过使用i--修改i,会影响到接下来的if条件,这些条件旨在查看i的原始值。所以你不应该改变i(也不应该改变j),而是将值分配给grid[i-1][j]而不修改i

  • bfs函数中,j索引错误地与grid.length进行了比较。它应该与grid[i].length进行比较,因为不能保证网格是正方形的。

  • 计数是针对每个变成腐烂状态的橙子都增加的,但这不是应该计数的内容。许多橙子在同一分钟内可能会变成腐烂状态,你只应该计算分钟数,而不是橙子数。为了正确计数,你应该做出两个更改:

    • 只有在收集了所有腐烂橙子并放入队列后,才调用初始的bfs调用,因为它们都属于第0分钟。

    • bfs函数本身中,将新的腐烂橙子添加到一个单独的队列中,这样你就知道哪些是在这一特定分钟内添加的。然后当原始队列变空时,将第二个队列移动到第一个队列,增加一分钟计数,然后重复。

  • 不是问题,但是不需要将ij作为参数传递给bfs,而且不需要将计数器的引用传递给它,而是让bfs 返回 计数。

我已经尽量不更改你的代码来使其工作:

class Solution {
    public int orangesRotting(int[][] grid) {
        Queue<String> q = new LinkedList<>();
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == 2) {
                    q.add("" + i + j);
                }
            }
        }
        // 仅当所有第0分钟腐烂橙子被识别时才调用BFS
        int count = bfs(grid, q);
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                System.out.println(grid[i][j]); // 不打印正确的值,未改为2
                if (grid[i][j] == 1) {
                    return -1;
                }
            }
        }
        return count;
    }

    private static int bfs(int[][] grid, Queue<String> q) {
        int count = 0;
        while (true) { // 每分钟一次迭代
            // 使用另一个队列进行下一分钟处理
            Queue<String> q2 = new LinkedList<>();
            // 将在本分钟变腐烂的橙子填充到新队列中
            while (!q.isEmpty()) {
                String s = q.remove();
                int i = Integer.parseInt(s.substring(0, 1));
                int j = Integer.parseInt(s.substring(1));
                if (i - 1 >= 0 && grid[i - 1][j] == 1) {
                    // 不要为每个单独的橙子增加计数!
                    // ...也不要更改i或j的值。
                    grid[i - 1][j] = 2;
                    q2.add("" + (i - 1) + j);
                }
                if (i + 1 < grid.length && grid[i + 1][j] == 1) {
                    grid[i + 1][j] = 2;
                    q2.add("" + (i + 1) + j);
                }
                if (j - 1 >= 0 && grid[i][j - 1] == 1) {
                    grid[i][j - 1] = 2;
                    q2.add("" + i + (j - 1));
                }
                // 与正确的长度进行比较
                if (j + 1 < grid[i].length && grid[i][j + 1] == 1) {
                    grid[i][j + 1] = 2;
                    q2.add("" + i + (j + 1));
                }
            }
            if (q2.isEmpty()) { // 没有新橙子变腐烂
                return count;
            }
            // 继续下一分钟:现在才增加计数
            count++;
            q = q2;
        }
    }
}

当然,肯定有更有效的方法来运行这段代码,例如使用数组代替队列。

英文:

Several issues:

  • The cells in column 0 or row 0 are never checked for infecting oranges. The comparison i - 1 &gt; 0 is not true when i is 1, yet you should also check grid[0][j]... The same issue occurs with j.

  • By modifying i with i--, you impact the next if conditions, which are intended to look at the original value of i. So you should not change the value of i (nor of j), but assign to grid[i-1][j] without modification of i.

  • In bfs, the j index is wrongly compared to grid.length. It should be compared against grid[i].length as the grid is not guaranteed to be square.

  • The count is increased for every orange that is made rotten, but that is not what should be counted. Many oranges can turn rotten in the same minute, and you should only count minutes, not oranges. To count correctly you should make two changes:

    • Only make the initial call to bfs when you have collected all rotten oranges in the queue, since they all belong to minute 0.

    • In the bfs function itself, add new rotten oranges to a separate queue, so you know which ones were added in this particular minute. Then when the original queue becomes empty, move the second queue to the first, account for a next minute, and repeat.

  • Not a problem, but there is no need to pass i and j as arguments to bfs, and instead of passing a reference to a counter, let bfs return the count.

I have tried to not change more than necessary in your code to make it work:

class Solution {
public int orangesRotting(int[][] grid) {
Queue&lt;String&gt; q = new LinkedList&lt;&gt;();
for(int i = 0; i &lt; grid.length; i++) {
for(int j = 0; j &lt; grid[i].length; j++) {
if(grid[i][j] == 2) {
q.add(&quot;&quot; + i + j);
}
}
}
// Only call BFS when all rotten oranges on &quot;minute 0&quot; are identified
int count = bfs(grid, q);       
for(int i = 0; i &lt; grid.length; i++) {
for(int j = 0; j &lt; grid[i].length; j++) {
System.out.println(grid[i][j]); //does NOT print correct value, not changed to 2
if(grid[i][j] == 1) {
return -1;
}
}
}      
return count;
}
private static int bfs(int[][] grid, Queue&lt;String&gt; q) {
int count = 0;
while(true) { // One iteration per minute
// Use another queue for the next minute
Queue&lt;String&gt; q2 = new LinkedList&lt;&gt;();
// Populate the new queue with oranges that get rotten in this minute
while(!q.isEmpty()) {
String s = q.remove();
int i = Integer.parseInt(s.substring(0,1));
int j = Integer.parseInt(s.substring(1));
if(i - 1 &gt;= 0 &amp;&amp; grid[i - 1][j] == 1) {
// Do not increase the counter for each separate orange!
// ...and do not change the value of i or j.
grid[i-1][j] = 2;
q2.add(&quot;&quot; + (i-1) + j);
}
if(i + 1 &lt; grid.length &amp;&amp; grid[i + 1][j] == 1) {
grid[i+1][j] = 2;
q2.add(&quot;&quot; + (i+1) + j);
}
if(j - 1 &gt;= 0 &amp;&amp; grid[i][j - 1] == 1) {
grid[i][j-1] = 2;
q2.add(&quot;&quot; + i + (j-1));
}
// Compare against the correct length
if(j + 1 &lt; grid[i].length &amp;&amp; grid[i][j + 1] == 1) {
grid[i][j+1] = 2;
q2.add(&quot;&quot; + i + (j+1));
}
}
if (q2.isEmpty()) { // No new oranges were turned rotten
return count;
}
// Continue for a next minute: only now increase the counter
count++;
q = q2;
}
} 
}

There are surely ways to make this run more efficiently, like using arrays instead of queues.

huangapple
  • 本文由 发表于 2020年9月26日 05:34:11
  • 转载请务必保留本文链接:https://go.coder-hub.com/64071567.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定